HDU 1711 Number Sequence (字符串匹配，KMP算法)

HDU 1711 Number Sequence (字符串匹配，KMP算法)

Description

Given two sequences of numbers : a1, a2, ...... , aN, and b1, b2, ...... , bM (1 <= M <= 10000, 1 <= N <= 1000000). Your task is to find a number K which make aK = b1, aK+1 = b2, ...... , aK+M−1 = bM. 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 a1, a2, ...... , aN. The third line contains M integers which indicate b1, b2, ...... , bM. 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

Http

HDU:https://vjudge.net/problem/HDU-1711

Source

字符串匹配，KMP算法

解决思路

就是KMP算法的运用，请参看我的这篇文章。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxN=1000001;
const int inf=2147483647;

int n,m;
int A[maxN];
int B[maxN];
int F[maxN];

int read();

int main()
{
int TT=read();
for (int ti=1;ti<=TT;ti++)
    {
        n=read();
        m=read();
for (int i=0;i<n;i++)
            A[i]=read();
for (int i=0;i<m;i++)
            B[i]=read();
        F[0]=-1;
for (int i=1;i<m;i++)
        {
int j=F[i-1];
while ((B[j+1]!=B[i])&&(j!=-1))
                j=F[j];
if (B[j+1]==B[i])
                F[i]=j+1;
else
                F[i]=-1;
        }
//for (int i=0;i<m;i++)
// cout<<F[i]<<' ';
//cout<<endl;
int i=0,j=0;
bool flag=0;
while (i<n)
        {
if (A[i]==B[j])
            {
                i++;
                j++;
if (j==m)
                {
                    cout<<i-j+1<<endl;
                    flag=1;
break;
                }
            }
else
if (j==0)
                i++;
else
                j=F[j-1]+1;
        }
if (flag==0)
            cout<<-1<<endl;
    }
return 0;
}

int read()
{
int x=0;
int k=1;
char ch=getchar();
while (((ch<'0')||(ch>'9'))&&(ch!='-'))
        ch=getchar();
if (ch=='-')
    {
        k=-1;
        ch=getchar();
    }
while ((ch<='9')&&(ch>='0'))
    {
        x=x*10+ch-48;
        ch=getchar();
    }
return x*k;
}