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.
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.
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;
}
转载于:https://www.cnblogs.com/SYCstudio/p/7195969.html
