题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1711
题意是输入两个数组,问能不能在文本数组s中找到模式数组p,输出最先的位置,如果找不到输出-1
思路就是kmp把字符串换成数组就好了,最后返回的是文本串中的位置减去模式串的长度,就是要求的最开始的位置。
AC代码:
#include <bits/stdc++.h>
#define maxn 1000005
#define ll long long
using namespace std;
int s[maxn], p[10005];
int Next[10005];
int T, n, m;
void init(){
int j = 0, k = -1;
memset(Next, -1, sizeof(Next));
while(j < m){
if( k == -1 || p[j] == p[k]){
k ++;
j ++;
Next[j] = k;
}
else k = Next[k];
}
}
int kmp(){
int i = 0, j = 0;
while(j < n){
if(i == -1 || p[i] == s[j]){
i ++;
j ++;
}
else{
i = Next[i];
}
if(i == m){
return j - m;
}
}
return -1;
}
int main()
{
scanf("%d", &T);
while(T--){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%d", &s[i]);
for(int i=0;i<m;i++)scanf("%d", &p[i]);
init();
int ans = kmp();
printf("%d\n", ans == -1 ? ans : ans + 1);
}
return 0;
}