Z 函数（扩展 KMP 算法）

约定下标从 0 开始。

Z 函数

定义 $z[i]$ 表示字符串 $s$ 和 $s[i..]$ （即从 $i$ 开始的部分）的最长公共前缀。

我们可以在 $O(n)$ 复杂度内计算出一个字符串的 Z 函数。（当然也可以哈希单 log 完成）

假设我们已经求出了 $z[0],z[1],\ldots,z[i-1]$ ，对于每个 $i$ ，将 $[i,i+z[i]-1]$ 称为它的 Z-box。

我们找出 $1\sim i-1$ 中右端点最靠右的 Z-box，记作 $[l,r]$ 。（初始时 $l=r=0$ ，不计 $z[0]$ 的 Z-box）

分类讨论：

$i\le r$ ：根据 Z 函数定义可知 $s[0..r-l]=s[l,r]$ ，则 $s[i..r]=s[i-l,r-l]$ ，那么 $z[i]\ge \min(r-i+1,z[i-l])$ 。令 $z[i]=\min(r-i+1,z[i-l])$ ，然后再暴力往后一位一位直至失配。
$i > r$ ：直接往后一位一位匹配直至失配。

复杂度说明：对于情况 1，只有当 $z[i-l]\ge r-i+1$ 时才会扩展，此时每往后匹配一位 $r$ 就会后移一位。对于情况 2，因为 $i>r$ ，所以每往后匹配一位 $r$ 就会至少后移一位。

因此在 $O(n)$ 时间内求出了整个字符串的 Z 函数。

可以发现这个过程和 Manacher 算法很相似。

代码：

vector<int> z_function(string s) {
    int n = s.length();
    vector<int> z(n);
    for(int i=1,l=0,r=0;i<n;i++) {
        if(i<=r)z[i]=min(r-i+1, z[i-l]); // 利用 Z-box 的信息
        while(i+z[i]<n && s[z[i]]==s[i+z[i]])++z[i]; // 暴力继续匹配
        if(i+z[i]-1>r)l=i,r=i+z[i]-1; // 更新 Z-box
    }
    return z;
}

（注意上面的代码没有算 $z[0]$ ，因为是平凡的，用处不太大就不管它了）

为了节省一点常数可以稍微修改一下（和上面代码是等价的，至于写哪个就见仁见智了）：

vector<int> z_function(string s) {
    int n = s.length();
    vector<int> z(n);
    for(int i=1,l=0,r=0;i<n;i++) {
        if(i<=r && z[i-l]<r-i+1)z[i]=z[i-l];
        else{
            z[i] = max(0,r-i+1);
            while(i+z[i]<n && s[z[i]]==s[i+z[i]])++z[i];
        }
        if(i+z[i]-1>r)l=i,r=i+z[i]-1;
    }
    return z;
}

模板题

P5410 【模板】扩展 KMP/exKMP（Z 函数）

构建字符串 $s=b+\circ+a$ 。然后计算 $s$ 的 Z 函数。（其中 $\circ$ 是任意不在 $a,b$ 中出现的字符）

$b$ 自己的后缀的 LCP 长度就是 $s$ 前面一部分的 Z 函数的值。
而 $b$ 与 $a$ 的每一个后缀的 LCP 长度是 $s$ 中后面部分 Z 函数的值，因为我们插入了一个在字符串中没有出现的 $\circ$ 字符，根据定义就能得到结果。

这启发我们 Z 函数可以 $O(n+m)$ 处理字符串匹配，而且可以求出从某一个位置开始最多可以匹配几个字符（这是 KMP 无法做到的）。

#include<bits/stdc++.h>
using namespace std;

using ll=long long;

vector<int> z_function(string s) {
    int n = s.length();
    vector<int> z(n);
    for(int i=1,l=0,r=0;i<n;i++) {
        if(i<=r && z[i-l]<r-i+1)z[i]=z[i-l];
        else{
            z[i] = max(0,r-i+1);
            while(i+z[i]<n && s[z[i]]==s[i+z[i]])++z[i];
        }
        if(i+z[i]-1>r)l=i,r=i+z[i]-1;
    }
    return z;
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    string a,b; cin>>a>>b;
    string s = b+"#"+a;
    auto z = z_function(s);
    z[0] = b.size();

    ll ans1 = 0;
    for(ll i=0;i<b.size();i++)ans1 ^= (i+1)*(z[i]+1);

    ll ans2 = 0;
    for(ll i=0;i<a.size();i++)ans2 ^= (i+1)*(z[i+b.size()+1]+1);

    cout << ans1 << '\n' << ans2 << '\n';
    return 0;
}