KMP算法实现模式串匹配
C++实现kmp算法,求出模式串NEXT的值,并给出第一个匹配串的起始位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
#include<iostream> #include<string> using namespace std; int main(){ string big,min; cin>>big>>min; int m,n,next[1000]; n=big.length(); m=min.length(); next[0]=-1; int i=0,j=0,k=-1; while(j<m-1){ if(k==-1||min[k]==min[j]){ k++;j++; next[j]=k; }else k=next[k]; } cout<<"模式串next值"<<endl; for(i=0;i<m;i++){ cout<<next[i]<<' '; } cout<<endl; j=0;i=0; while(i<n&&j<m){ if(big[i]==min[j]||j==-1){ i++;j++; }else{ j=next[j]; } } if(j>=m){ cout<<i-m+1<<endl; }else{ cout<<"未匹配"<<endl;} return 0; } |