以下数组下标均从0开始

需要解决的问题：

给定两个字符串S，T（长度分别为n，m），定义extend[i]等于s[i]…s[n-1]与T最长相同前缀的长度，求出所有extend数组

举个extend数组的例子：

结果很显然，这里不再解释了

算法流程

假如说现在我们已经遍历到了S串的位置i，对于主串S我们定义从a，p为从a开始能匹配到的最右边界，这也就意味着s[p] != t[p-a]

在上图中根据上面的定义显然s[a..p)与t[0..p-a)相同

这里我们还需要引进一个辅助数组next，next[i]所代表的是在模式串T中，第t[i]到模式串结束这个字符串与模式串T本身所拥有的最大公共前缀长度。

下面举个例子便于理解：

拥有了以上几个定义，我们来分类讨论一下三种情况：

情况一：

观察上图，我们考虑一个事情：若 i+next[i-a] < p 代表着什么

图中所标出的区域3 与区域2即代表着next[i-a]，而根据我们上面的定义，区域1和区域2又是相同的，那么我们就根据传递性得到区域1与区域3也是相同的，也即代表着主串S中以i开始与模式串T的最长前缀是多长。

此时我们便可得 extend[i] = next[i-a]

情况二：

如果 i+next[i-a] == p 继续观察上图

首先和上面的情况类似，根据传递性可以得到s[i..p-1]与t[p-i-1]相等。

现在的关键在于，我们刚才在假设时指出的是s[p]!=t[p-a]，但是这并不意味着s[p]!=t[p-i]，因为根据刚才的设定t[p-i]!=t[p-a]。所以我们只需从这一位开始进行逐位比较就可以得出extend[i]

情况三：

此时 i+next[i-a] > p

实际上看了前两种情况之后这种情况反而简单。

因为我们知道块2和块3相同，但是块1却和块2不同。那么是从哪里开始不同的呢？就是s[p]!=t[p-a]

所以此时： extend[i] = p-i

以上就是extend的求法，那么next怎么求？

观察我们对上面的定义不难看出，next就是模式串和主串相同的求extend

于是我们就得到了如下代码：

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define maxn 10000010
typedef long long ll;
using namespace std;
#define rep(i, n, args...) for (ll i = 0, ##args; i < n; i++)
#define repr(i, s, e, args...) for (ll i = s, ##args; i < e; i++)
#define erg(i, u, args...) for (ll i = vtx[u], ##args; ~i; i = eg[i].nxt)
#define fulset(x, v) memset(x, v, sizeof(x));
/* 求解 T 中 next[]，注释参考 GetExtend() */
void GetNext(string & T, int & m, int next[])
{
    int a = 0, p = 0;
    next[0] = m;
    
    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];
    }
}

/* 求解 extend[] */
void GetExtend(string & S, int & n, string & T, int & m, int extend[], int next[])
{
    int a = 0, p = 0;
    GetNext(T, m, next);
    
    for (int i = 0; i < n; i++)
    {
        if (i >= p || i + next[i - a] >= p) // i >= p 的作用：举个典型例子，S 和 T 无一字符相同
        {
            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];
    }
}

int main()
{
    int next[100];
    int extend[100];
    string S, T;
    int n, m;
    
    while (cin >> S >> T)
    {
        n = S.size();
        m = T.size();
        GetExtend(S, n, T, m, extend, next);
        
        // 打印 next
        cout << "next:   ";
        for (int i = 0; i < m; i++)
            cout << next[i] << " ";
        
        // 打印 extend
        cout << "\nextend: ";
        for (int i = 0; i < n; i++)
            cout << extend[i] << " ";
        
        cout << endl << endl;
    }
    return 0;
}