首页 > 代码库 > 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。