首页 > 代码库 > C 题 KMP中next[]问题

C 题 KMP中next[]问题

2024-07-14 07:33:36   224人阅读

题目大意：

找到能够进行字符串匹配的前缀

 

这题只要一直求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 }

 


联系
我们