EX-KMP，和 Manacher 回顾

给定两个字符串，你要求出：

的函数数组，即与的每一个后缀的 LCP（最长公共前缀）长度。

在国外，这个 EX-KMP 算法叫做「Z 函数」，可见和 KMP 关系并不大。而求这个函数的值的算法过程倒是和 Manacher 有点像。

首先回顾一下 Manacher 算法：

Manacher 算法

给出一个只由小写英文字符组成的字符串 ,求中最长回文串的长度。字符串长度为。。

我们首先将原本的字符两两之间和首尾都插入同一种奇怪的字符，这样就可以使回文中心不再局限于字符之上，而是也可以包含两个字符中间的地方，也就是回文串长度为偶数也可以算出来。

我们定义数组表示以点为回文中心，在新字符串中的最大回文半径（包含本身）长度是多少。这样的话，最终的答案就是。

我们开始遍历这个数组。我们维护一个目前的能包含并且右端点尽量靠右的回文串。

注意：Manacher 这个算法的精髓就是利用了回文串有对称中心并且左右对称的性质。这个性质可以将现在要算的给定位到之前算过的数组里去。

例子如下图：

如果并且是通过前面已经算出来的来更新，由于只有是已知的，所以的回文半径也最多就只能扩展到。式子就是。然后后面的就只能暴力枚举更新回文半径。

而如果以为回文半径的回文串，它的右端点超过了目前的，那么就设，同时更新，之后继续遍历下一个字符。

良好地利用了回文串的性质，使得 Manacher 算法的时间复杂度只有，足以通过此题。

void solve(){
    cin>>(a+1);
    n = strlen(a+1);
    s[0] = s[1] = '%'; //s[0] 其实想填什么特殊字符就填什么特殊字符。因为要对应的是后面的空格来保证不越界。
    rn = 1;
    for(int i=1;i<=n;i++){
        s[++rn] = a[i];
        s[++rn] = '%';
    }
    int mid = 0, mr = 0;
    for(int i=1;i<=rn;i++){
        if(i <= mr) ans[i] = min(ans[(mid<<1) - i], mr - i + 1);
        while(s[i - ans[i]] == s[i+ ans[i]]) ans[i] ++;
        //i + ans[i]即i + ans[i] - 1 + 1;就是他的右边界+1, i - ans[i]同理
        if(i + ans[i] > mr){
            mr = i + ans[i] - 1;
            mid = i;
        }
    }
    int result = 0;
    for(int i=1;i<=rn;i++){
        result = max(result, ans[i]);
    }
    cout<<result - 1;
}

EX-KMP 算法

而 EX-KMP 算法其实和 Manacher 算法思想类似，EX-KMP 算法是维护了一个「小盒子」，这个盒子和是完全相同的，也就是维护了一个右端点尽量靠右的匹配段。

我们利用这个和完全相同的性质，当在盒内时，可以将转化为。而又因为目前最多只遍历到了，后面未知，所以还要和取个。

所以当时，。后面依然需要 while 暴力往右搜索可不可以继续匹配，如果可以的话 ++。依然当时，更新。

// 此处字符串为 t，长度为 m。
void get_Z(){
    z[1] = m;
    for(int i=2, l=0, r=0;i<=m;i++){
        if(i<=r) z[i] = min(z[i-l+1], r-i+1);
        while(t[1+z[i]] == t[i+z[i]]) z[i] ++;
        if(i+z[i]-1>r) l=i, r=i+z[i]-1;
    }
}