C++实现KMP算法
浏览数：21 /
时间：2015年06月08日
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
void NEXT(const string &T, vector<int> &next)
{
//按模式串生成vector,next(T.size())
next[0] = -1;
for(int i = 1; i < T.size(); i++)
{
int j = next[i - 1];
while(T[i] != T[j + 1] && j >= 0)
j = next[j];
//递推计算
if(T[i] == T[j + 1])
next[i] = j + 1;
else
next[i] = 0;
}
}
string::size_type COUNT_KMP(const string &S, const string &T)
{
//利用模式串T的next函数求T在主串S中的个数count的KMP算法
//其中T非空，
vector<int> next(T.size());
NEXT(T, next);
string::size_type index, count=0;
for(index=0; index < S.size(); ++index)
{
int pos=0;
string::size_type iter = index;
while(pos < T.size() && iter<S.size())
{
if(S[iter] == T[pos])
{
++iter;
++pos;
}
else
{
if(pos == 0)
++iter;
else
pos = next[pos - 1] + 1;
}
}
if(pos == T.size() && (iter - index) == T.size())
++count;
}
return count;
}
int main()
{
string S, T;
cout<<"请输入主串（参照的）"<<endl;
cin>>S;
cout<<"请输入子串（要查找的）"<<endl;
cin>>T;
string::size_type count =COUNT_KMP(S,T);
cout<<"一共有 "<<count<<" 个子串"<<endl;
return 0;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
