讲解参考：https://www.jianshu.com/p/107e47994d49

要点总结：

（1）目的：母串S，len(S)=n，子串T, len(T)=m， 两个字符串存储时下标都从0开始，suffix（i）表示S串中从下标i开始的后缀，扩展kmp算法可以求每个suffix(i)和T的最长公共前缀长度

（2）nxt[i]表示T串的suffix(i)和T串的最长公共前缀长度

（3）Extend[i]表示S串的suffix(i)和T串的最长公共前缀长度

（4）nxt数组和Extend数组的求法相同，在求nxt时，T串既充当S串又充当T串

（5）求nxt[]时要预处理出nxt[0]和nxt[1]，求Extend[]时，因为nxt数组已经求出，所以只需预处理出Extend[0]即可

 

模版：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000010; //字符串长度最大值
int nxt[maxn],Extend[maxn];
char s1[maxn],s2[maxn];
//预处理计算nxt数组
void getnxt(char str[])
{
    int i=0,j,po,len=strlen(str);
    nxt[0]=len; //初始化nxt[0]
    while(str[i]==str[i+1] && i+1<len) i++; nxt[1]=i; //计算nxt[1]
    po=1; //初始化po的位置
    for(i=2;i<len;i++)
    {
        if(nxt[i-po]+i < nxt[po]+po) //第一种情况，可以直接得到nxt[i]的值
            nxt[i]=nxt[i-po];
        else //第二种情况，要继续匹配才能得到nxt[i]的值
        {
            j = nxt[po]+po-i;
            if(j<0) j=0; //如果i>po+nxt[po],则要从头开始匹配
            while(i+j<len && str[j]==str[j+i]) j++; nxt[i]=j;
            po=i; //更新po的位置
        }
    }
}

//计算Extendend数组
void EXKMP(char s1[],char s2[])
{
    int i=0,j,po,len=strlen(s1),l2=strlen(s2);
    getnxt(s2); //计算子串的nxt数组
    while(s1[i]==s2[i] && i<l2 && i<len) i++; Extend[0]=i;
    po=0; //初始化po的位置x
    for(i=1;i<len;i++)
    {
        if(nxt[i-po]+i < Extend[po]+po) //第一种情况，直接可以得到Extendend[i]的值
            Extend[i]=nxt[i-po];
        else //第二种情况，要继续匹配才能得到Extendend[i]的值
        {
            j = Extend[po]+po-i;
            if(j<0) j=0; //如果i>Extendend[po]+po则要从头开始匹配
            while(i+j<len && j<l2 && s1[j+i]==s2[j]) j++; Extend[i]=j;
            po=i; //更新po的位置
        }
    }
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%s", s1);
    scanf("%s", s2);//s2是子串
    EXKMP(s1,s2);
    int len = strlen(s1);
    for(int i = 0; i < len; i++)
        printf("suffix(%d):%s  和子串的最长公共前缀长度为：%d\n",i, s1+i, Extend[i]);
    return 0;
}

测试样例：第二个字符串为子串

aabaaaab
aaabc

 输出：

suffix(0):aabaaaab  和子串的最长公共前缀长度为：2
suffix(1):abaaaab  和子串的最长公共前缀长度为：1
suffix(2):baaaab  和子串的最长公共前缀长度为：0
suffix(3):aaaab  和子串的最长公共前缀长度为：3
suffix(4):aaab  和子串的最长公共前缀长度为：4
suffix(5):aab  和子串的最长公共前缀长度为：2
suffix(6):ab  和子串的最长公共前缀长度为：1
suffix(7):b  和子串的最长公共前缀长度为：0