Number Sequence

HDOJ-1711

1.这里使用的算法是KMP算法，pi数组就是前缀数组。

2.代码中使用到了一个技巧就是用c数组看成是复合字符串，里面加一个特殊整数位-1000006，因为它永远不会出现在数组中。

3.额外需要注意的就是，需要加快速输入输出语句，因为涉及到的数据量有点大，所以会超时，当然，也可以选用scanf也可以。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

int n,m;

int a[1000006],b[10004];

int pi[1000006];

int c[1010010];

void Pi(int len){

    memset(pi,0,sizeof(pi));

    int n=len;

    pi[0]=0;

    for(int i=1;i<n;i++){

        int j=pi[i-1];

        while(j>0&&c[i]!=c[j]){

            j=pi[j-1];

        }

        if(c[i]==c[j])

            j++;

        pi[i]=j;

    }

}

int main(){

    ios::sync_with_stdio(false);//不加这两条语句会超时

    cin.tie(0);

    int t;

    cin>>t;

    while(t--){

        cin>>n>>m;

        int a1,b1;

        for(int i=0;i<n;i++){

           cin>>a[i];

           c[i]=a[i];

        }

        for(int j=0;j<m;j++){

            cin>>b[j];

            c[j]=b[j];

        }

        c[m]=-1000006;

        for(int i=m+1;i<n+m+1;i++){

           c[i]=a[i-m-1];

        }

        Pi(m+n+1);

        int ans=-1;

        for(int i=m+1;i<n+1+m;i++){

            //cout<<pi[i]<<endl;

            if(pi[i]==m){

                ans=i-(m-1)-(m+1);

                ans++;

                break;

            }

        }

        cout<<ans<<endl;

    }

    return 0;

}

巴特西

HDOJ-1711(KMP算法)

Number Sequence

HDOJ-1711

最新文章

热门文章