KMP算法实现模式串匹配

作者: Rememberautumn 分类: 算法与数据结构发布时间: 2015-04-14 15:15 阅读: 1,948

C++实现kmp算法，求出模式串NEXT的值，并给出第一个匹配串的起始位置。

#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;

}

如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！