KMP 알고리즘 문자열 비교

/*
KMP algorithm
http://www.cnblogs.com/dolphin0520/archive/2011/08/24/2151846.html
*/
#include<iostream>  
#include<string>  
using namespace std;  

//           
int compare(string s1,string s2)
{
	int i=0,j=0;
	while(i<(s1.length()-s2.length()) )
	{

		while(s1[i]==s2[j] )
		{  
			
			cout<<"s1["<<i<<"]"<<s1[i]<<endl;
			cout<<"s2["<<j<<"]"<<s2[j]<<endl;
			i++;
			j++;
			if (s2.length()==j)
			{
				//return i-s2.length();
				cout<<"right"<<endl;
				return 1;
			}
		}
		i=i-j+1;
		j=0;
	}	
	return 0;
}

/*KMP      
    next[0]=-1，  next[j]=k,  P[0...k-1]==P[j-k,j-1]
1) P[j]==P[k]，  P[0..k]==P[j-k,j]，   ，next[j+1]=next[j]+1=k+1;
2) P[j]!=P[k]，              ，        ，k     ，
  k=next[k]
*/
void getNext_recursion(string s2,int next[])
{
	int j=0,k=-1;
	next[0]=-1;
	while (j<s2.length()-1)
	{
		if (k==-1||s2[j]==s2[k])
		{
			j++;
			k++;
			next[j]=k;//next[j++]=k++;
		}
		else
			k=next[k];
	}
}

int KMP(string s1,string s2)
{
	int next[100];
	getNext_recursion(s2,next);
	int i=0,j=0;
	while(i<s1.length() )
	{
	    if(j==-1||s1[i]==s2[j])
		{
			i++;
			j++;
		}
		else
		{
		    j=next[j];
		}

		if (s2.length()==j)
		{
			return i-j;
		}

	}	
return 0;

}
int main()  
{  

	string s1="ababcababa",s2="ababa";
	/*cout<<"   text "<<endl;
	cin>>s1;
	cout<<"   query "<<endl;
	cin>>s2;*/
	cout<<s1<<endl;
	cout<<s2<<endl;
	//cout<<compare(s1,s2);
	cout<<KMP(s1,s2);
	cout<<endl;  
	return 0;  
}