reference: Rabin-Karp and Knuth-Morris-Pratt Algorithms By TheLlama– TopCoder Member https://www.topcoder.com/community/data-science/data-science-tutorials/introduction-to-string-searching-algorithms/ // to be improved
nums[MAXN];int cnums[MAXM];int ffunc[MAXM]={0};int main() {#ifndef ONLINE_JUDGEfreopen(“in.txt”,”r”,stdin);#endifint T,n,m,i,j,k, res;int *p,*pend, *q, *r, *rend;if(scanf(“%d”,&T)!=1) return -1;while(T–>0 && scanf(“%d%d”,&n,&m)==2 && n>=m && m>0) {for(i=1;i<=n;++i) scanf(“%d”,&nums[i]);for(i=1;i<=m;++i) scanf(“%d”,&cnums[i]);for(i=2;i<=m;++i) {for(j=ffunc[i-1];;j=ffunc[j]) {if(cnums[j+1]==cnums[i] || j==0 && –j) break;}ffunc[i]=j+1;}for(i=1, k=0;;) {if(nums[i]==cnums[k+1]) { ++k; }else if(k>0) { k=ffunc[k]; continue; }if(++i>n || k>=m) break;}res=k!=m?-1:i-m;printf(“%d\n”,res);}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。// ps. If in any way improment can be achieved, better performance or whatever, it will be well-appreciated to let me know, thanks in advance.
人生就像一杯没有加糖的咖啡，喝起来是苦涩的，
