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

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

C++实现KMP算法