kmp模板题
上模板就行了
#include<iostream> #include<algorithm> #include<string> #include<vector> using namespace std; const int max_n = 1e5+100; int net[max_n]; void getnext(int p[],int size) { int i = 0;int j = -1; net[0] = -1; while (i < size) { if (j == -1 || p[i] == p[j]) { ++i;++j; if (p[i] != p[j]) net[i] = j; else net[i] = net[j]; } else j = net[j]; } } int kmp(int s[],int ssize,int p[],int psize) { register int i = 0;register int j = 0; int res = 0; while (i < ssize) { if (j == -1 || p[j] == s[i]) { ++i;++j; } else j = net[j]; if (j == psize) { return i-psize+1; ++res; j = net[j]; } }return -1; } int n,m; int p[12000]; int s[1100000]; int main(){ int T;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]); getnext(p,m); printf("%d\n",kmp(s,n,p,m)); } }