拓展KMP算法 入门+模板

拓展KMP算法入门

博客推荐

扩展KMP算法, 图很形象，代码写的也很清晰，下面的模板就是出自该博客文章。

拓展KMP是求母串S长度为n和子串T长度为m,求S的每一个后缀子串与T的前缀子串匹配的最长长度。

代码实现

//求解模式串T的next数组，这个函数和下面的函数几乎相同
void getnext(string &T, int m, int[] next)
{
	int a = 0, p = 0;
    next[0] = m; //T字符串自身和自身匹配
    for(int i=1; i<m; i++)
    {
        if(i >= p || i + next[i - a] >= p)
        {
            if( i >= p)
                p = i;
            while(p < m && T[p] == T[p - i])
                p++;
            next[i] = p - i;
            a = i;
        }
        else next[i] = next[i - a];
	}
}

void getextend(string &S, int n, string &T, int m, int[] extend)
{
    int a=0, p=0;
    getnext(T, m, next);
    for(int i=0; i<n; i++)
    {
        if(i >= p || i + next[i - a] >= p)
        {
            if(i >= p)
                p = i;
            while(p < n && p - i < m && S[p] == T[p - i])
                p++;
            extend[i] = p - i;
            a = i;
		}
        else extend[i] = next[i-a];
	}
}