KMP算法

刚开始学KMP算法，感觉还挺简单的，唯一有点难理解的是next数组的理解，不过自己操作一遍也就明白了，写了以下代码并轻松过了HDU2203这道水题，下面是我的代码！

#include<iostream>
#include<string>
using namespace std;
#define N 100005
int next[N];
string str_s,str_m;
void GetNextEx()
{
int k=-1,j=0;
next[0]=-1;
int siz=str_s.size()-1;
while(j<siz)
{
	if(k==-1||str_s[k]==str_s[j])
	{
      k++;
      j++;
	  next[j]=k;
    }
    else 
    k=next[k];
}

}
int KMP()
{
    int i=0,j=0,siz=str_m.size(),siz1=str_s.size();
	if(siz<siz1)
		return -1;
    while(i<siz)
    {
        if(j==-1||str_m[i]==str_s[j])
        {
            i++;
            j++;
        }
        else
        {
            j=next[j];       
        }
        if(j==siz1)
            return i-siz1;;
    }
    return -1;
}

int main()
{   
	while(cin>>str_m>>str_s)
	{
         GetNextEx();
		 str_m+=str_m;
		 if(KMP()==-1)
		 cout<<"no"<<endl;
		 else
			 cout<<"yes"<<endl;
	}
	return 0;
}

KMP算法,布布扣,bubuko.com

KMP算法

原文：http://blog.csdn.net/alop_daoyan/article/details/24298911