Number Sequence（kmp模板）

Bertha 。 2022-08-02 13:39 152阅读 0赞

# Number Sequence #

**Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 14210    Accepted Submission(s): 6306**

Problem Description

Given two sequences of numbers : a\[1\], a\[2\], ...... , a\[N\], and b\[1\], b\[2\], ...... , b\[M\] (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make a\[K\] = b\[1\], a\[K + 1\] = b\[2\], ...... , a\[K + M - 1\] = b\[M\]. If there are more than one K exist, output the smallest one.

Input

The first line of input is a number T which indicate the number of cases. Each case contains three lines. The first line is two numbers N and M (1 <= M <= 10000, 1 <= N <= 1000000). The second line contains N integers which indicate a\[1\], a\[2\], ...... , a\[N\]. The third line contains M integers which indicate b\[1\], b\[2\], ...... , b\[M\]. All integers are in the range of \[-1000000, 1000000\].

Output

For each test case, you should output one line which only contain K described above. If no such K exists, output -1 instead.

Sample Input

2
    13 5
    1 2 1 2 3 1 2 3 1 3 2 1 2
    1 2 3 1 3
    13 5
    1 2 1 2 3 1 2 3 1 3 2 1 2
    1 2 3 2 1

Sample Output

6
    -1

Source

[HDU 2007-Spring Programming Contest][]

#include<iostream>
    using namespace std;
    const int MAXN = 1111111,MAXM = 11111;
    int T[MAXN],P[MAXM],Next[MAXM];
    void get_next(int *a,int len){
        int i=-1,j=0;
        Next[0]=-1;
        while(j<len){
            if(i == -1 || a[i] == a[j]){
                if(a[++i] == a[++j])Next[j]=Next[i];
                else Next[j]=i;
            }else i=Next[i];
        }
    }
    
    int KMP(int *a,int *b,int lena,int lenb){ //在b中找a
        get_next(a,lena);
        int i=0,j=0;
        while(i<lena && j<lenb){
            if(i == -1 || a[i] == b[j])++i,++j;
            else i=Next[i];
        }
       if(i==lena)//j字符串结束位置，lena就是a的长度，这样计算的是字符串的开始位置!
       {
           return j-lena+1;
       }
       else
       {
           return -1;
       }
    }
    int main()
    {
        int n,m,t,i;
        cin>>t;
        while(t--)
        {
            cin>>n>>m;
            for(i=0;i<n;i++)
            {
                scanf("%d",&T[i]);
            }
            for(i=0;i<m;i++)
            {
                scanf("%d",&P[i]);
            }
            if(m>n)
            {
                cout<<-1<<endl;
            }
            else
            {
                cout<<KMP(P,T,m,n)<<endl;
            }
        }
    }

[HDU 2007-Spring Programming Contest]: http://acm.hdu.edu.cn/search.php?field=problem&key=HDU+2007-Spring+Programming+Contest&source=1&searchmode=source