废话不多说，上模板

#include
      
       const int maxn = 1e6 + 10;int Next[maxn], extend[maxn], moL, strL;///Next数组、extend数组、模式串长度、母串长度char mo[maxn], S[maxn];///模式串、母串void GetNext()///求解模式串 mo 的 Next 数组{    Next[0] = moL;    int a, p;    for (int i = 1, j = -1; i < moL; i++, j--){        if (j < 0 || i + Next[i - a] >= p){            if (j < 0) p = i, j = 0;            while (p < moL && mo[p] == mo[j]) p++, j++;            Next[i] = j;            a = i;        } else Next[i] = Next[i - a];    }}void GetExtend()///模式串 mo 对主串 S 求解 extend 数组{    GetNext();    int a, p; ///记录匹配成功的字符的最远位置p，及起始位置a    for (int i = 0, j = -1; i < strL; i++, j--){ ///j即等于p与i的距离，其作用是判断i是否大于p（如果j<0，则i大于p）        if (j < 0 || i + Next[i - a] >= p){ ///i大于p（其实j最小只可以到-1，j<0的写法方便读者理解程序）            if (j < 0) p = i, j = 0; ///如果i大于p            while (p < strL && j < moL && S[p] ==  mo[j])                p++, j++;            extend[i] = j;            a = i;        } else extend[i] = Next[i - a];    }}
      

 

本文实际就是为了记录一下较好的拓展KMP资料...........

 

问题提出 : 给出子串以及母串，我们定义extend[i]表示从母串的第 i 字符开始到最后（也就是从 i 位置开始的后缀 ）与子串的最长公共前缀长度，现在要求在线性时间内对于母串的所有位置求出extend值即extend[ 0~strlen(母串)-1 ]

 

参考 : 在网上看了好多博客，都不能看的非常明白，直到遇到这个图文并茂的博客，强烈推荐 ==> 

 

完了嘛？嗯，完了……