首页 > 代码库 > C 题 KMP中next[]问题
C 题 KMP中next[]问题
题目大意:
找到能够进行字符串匹配的前缀
这题只要一直求next,直到next为0停止,记得答案是总长减去next的长度
1 #include <iostream> 2 #include <cstdio> 3 #include<string> 4 using namespace std; 5 6 #define N 1000100 7 int a[N],b[N],next[N]; 8 int m; 9 void getNext(){10 next[0]=0;11 next[1]=0;12 for(int i=1;i<m;i++){13 int j=next[i];14 while(b[j]!=b[i]&&j) j=next[j];15 if(b[j]==b[i]) next[i+1]=j+1;16 else next[i+1]=0;17 }18 }19 20 int main()21 {22 int T,count;23 cin>>T;24 string s;25 for(int i=1;i<=T;i++){26 cin>>s;27 m=s.length(),count=0;28 int t=m;29 for(int k=0;k<m;k++) b[k]=s.at(k);30 getNext();31 //a[count++]=m;32 33 while(next[m])34 {35 a[count++]=t-next[m];36 m=next[m];37 }38 cout<<"Case #"<<i<<": "<<count+1<<endl;39 for(int i=0;i<count;i++) cout<<a[i]<<‘ ‘;40 cout<<t<<endl;41 }42 return 0;43 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。