kmp.cpp

来自「经典算法实现」· C++ 代码 · 共 112 行

#include "KMP.h"


void prePostMatch( const string  str,int* ass){

		ass[1] =0;
		
		int tail=2,temp=0;

		for (;tail<str.size();)
		{

			if (str[tail-1]==str[temp])
			{
				ass[tail]=temp+1;
				temp++;
				tail++;
			
			}

			else if (temp ==0)
			{
			ass[tail]=0;
			tail++;
			//temp =0;
			}

			else {
				temp = ass[temp];
			}
		}

		while(true)
		{

			if (str[tail-1]==str[temp])
			{
				ass[0]=temp+1;
				break;
				//temp = ass[tail];
			}

			else if (temp ==0)
			{
				ass[0]=0;
				 break;
				//temp =0;
			}

			else {
				temp = ass[temp];
			}

		
		} 
}


int KMP(const string strA,string strSub){

	int *ass = new int [strSub.size()];

	prePostMatch(strSub,ass );

	int i=0,j=0;

//	for (;i<strSub.size() && j<strA.size();)
	for (;j<strA.size();)
	{
		if (strSub[i]==strA[j])   {	i++;		j++; 	} 
		else if (i==0)		j++;
	    else	i = ass[i];
		if (i==strSub.size()) { cout<< j-i<<endl; i=ass[0];}

	}

	//if(i!=strSub.size()) return -1;

	//return j-i;

	return 0;

}


/*j:=0;
for i:=1 to n do
begin
while (j>0) and (B[j+1]<>A[i]) do j:=P[j];
if B[j+1]=A[i] then j:=j+1;
if j=m then
begin
writeln('Pattern occurs with shift ',i-m);
j:=P[j];
end;
end;
*/

int main(){
	
	string test ="cccababababcabab";
	string sub = "abab";

	cout<< test.size()<<endl;

//	int pp = prePostMatch(sub,4);

	KMP(test,sub);
	
	//	cout<<pp<<endl;

}