KMP 算法 C++
#include <iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
void Compute_Prefix(string p,int prefix[],int length)
{
int k=0;
prefix[0]=0;
for(int i=1;i<length;i++)
{
while(k>0&&p[i]!=p[k])
{
k=prefix[k-1];
}
if(p[k]==p[i])
{
k=k+1;
}
prefix[i]=k;
}
}
void KMP_Matcher(string P,string T)
{
int length_P=P.length();
int length_T=T.length();
int i,q=0;
int* prefix=new int[length_P];
Compute_Prefix(P,prefix,length_P);
for(i=0;i<length_T;i++)
{
while(q>0&&P[q]!=T[i])
{
q=prefix[q-1];
}
if(P[q]==T[i])
{
q=q+1;
}
if(q==length_P)
{
cout<<(i-length_P+1)<<endl;
q=prefix[q-1];
}
}
}
int main(int argc, char *argv[])
{
string stra="AABA";
string strb="AABAACAADAABAAABAA";
KMP_Matcher(stra,strb);
return 0;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
