首页 > 代码库 > HDU 1711 Number Sequence

HDU 1711 Number Sequence

经典kmp

 

 1 #include <iostream> 2 #include <cstdio> 3 using namespace std; 4  5     int n,m; 6     int a[1000010],b[10010],next[10010]; 7  8 void getnext (int *s,int *next){ 9     next[0]=next[1]=0;10     for (int i=1;i<m;i++){11         int j=next[i];12         while (j&&s[i]!=s[j])13             j=next[j];14         next[i+1]=s[i]==s[j]?j+1:0;15     }16 }17 18 int kmp (int *a,int *b,int *next){19     getnext (b,next);20     int j=0;21     for (int i=0;i<n;i++){22         while (j&&a[i]!=b[j])23             j=next[j];24         if (a[i]==b[j])25             j++;//cout<<j<<" ";26         if (j==m)27             return i-m+2;28     }29     return -1;30 }31 32 int main (){33     int t;34     scanf ("%d",&t);35     while (t--){36         scanf ("%d %d",&n,&m);37         for (int i=0;i<n;i++)38             scanf ("%d",&a[i]);39         for (int i=0;i<m;i++)40             scanf ("%d",&b[i]);41         int ans=kmp (a,b,next);42         printf ("%d\n",ans);43     }44     return 0;45 }