KMP match

kmp.md

##KMP match

KMP算法的关键在于求算next[]数组的值，即求算模式串每个位置处的最长后缀与前缀相同的长度， 而求算next[]数组的值有两种思路，第一种思路是用递推的思想去求算，还有一种就是直接去求解(略)。

递推:

• 根据定义next[0]=-1，假设next[j]=k, 即P[0...k-1]==P[j-k,j-1]
• 若P[j]==P[k]，则有P[0..k]==P[j-k,j]，很显然，next[j+1]=next[j]+1=k+1
• 若P[j]!=P[k]，则可以把其看做模式匹配的问题，即匹配失败的时候，k值如何移动，显然k=next[k]

        void getNext(char* p,vector<int>& next)
        {
        	int j,k;
        	next[0]=-1;
        	j=0;
        	k=-1;
        	while(j<strlen(p)-1)
        	{
        		if(k == -1 || p[j] == p[k])
        		{
        			/*
        			If p[j] == p[k]
        			That p[0..k] = p[j-k..j]
        			Thus next[j+1] = next[j]+1 = k+1;
        			*/
        			next[++j]=++k;
        		}
        		else
        		{
        			k=next[k];
        		}
                //优化判断
                /*
                if(k == -1 || p[j] == p[k])
                {
                    ++j;
                    ++k;
                    if(p[j] != p[k])
                    {
                        next[j] = k;
                    }
                    else
                    {
                        next[j] = next[k];
                    }
                }
                else
                {
                    k = next[k];
                }
                */
        	}
        }
        int KMP(char* s, char* p)
        {
        	vector<int> next(strlen(p),0);
        	int i=0,j=0;
        	getNext(p,next);
        	while(i<strlen(s))
        	{
        		if(j == -1 || s[i] == p[j])
        		{
        			i++;
        			j++;
        		}
        		else
        		{
        			j = next[j];
        		}
        		if(j == strlen(p))
        		{
        			return i-j;
        		}
        	}
        	return -1;
        }