前缀函数-KMP-Z函数

前缀函数

(真)前缀/(真)后缀

前缀 $Prefix(S,i)$ 是指从串首开始到某个位置 $i$ 结束的一个子串，即 $Prefix(S, i)=S[0..i]$ 。真前缀指除了 $S$ 本身的前缀。
后缀 $Suffix(S,i)$ 是指从某个位置 $i$ 开始到字符串末尾的一个子串，即 $Suffix(S, i)=S[i..|S|-1]$ 。真后缀指除了 $S$ 本身的后缀。

前缀函数定义

给定一个长度为 $n$ 的字符串 $s$ ，其前缀函数被定义为一个长度为 $n$ 的数组 $\pi$ 。其中 $\pi [i]$ 的定义是：

如果子串 $s[0...i]$ 存在相等的真前缀与真后缀： $s[0...k-1]$ 和 $s[i-(k-1)...i]$ ，那么 $\pi[i]$ 就是相等的真前缀的长度的最大值，即 $\pi[i] = max(k)$ ，否则 $\pi[i] = 0$ ；
特别地，规定 $\pi[0] = 0$ 。

例如字符串abaab，其前缀函数数组为 $[0,0,1,1,2]$ 。

前缀函数计算方法

朴素的 $O(n^3)$ 解法不再赘述，这里直接介绍一种 $O(n)$ 复杂度的算法，也是下面介绍的KMP算法的基础。假设目前所求为 $next[i]$ ， $next[0..i-1]$ 已全部计算完成。令 $j=next[i-1]$ ，如下图所示：

尝试比较 $s[i]$ 与 $s[j]$ 是否相同：

若相同，则说明 $s[i]$ 可以沿用前缀 $next[i-1]$ ，即 $next[i] = next[i-1]+1$ ;
若不同，循环尝试是否可以沿用前缀 $next[j-1]$ ，直到 $s[i]$ 与 $s[j]$ 相同或 $j$ 为0；

该算法只需要利用 $s[i]$ 左侧的 $\pi$ 值，不需要进行任何字符串的比较，可以在 $O(n)$ 时间内完成。代码如下所示：

// 求字符串word的前缀函数数组
public int[] getNext(String word){
    int[] next = new int[n];
    for(int i = 1;i < n;++i){
        int j = next[i-1];
        while(j != 0 && word.charAt(i) != word.charAt(j)) j = next[j-1];
        if(word.charAt(i) == word.charAt(j)) ++j;
        next[i] = j;
    }
    return next;
}

KMP算法

核心思想

KMP常用于字符串匹配任务，例如找到模式串 $s2$ 与主串 $s1$ 的所有匹配的下标。常规的暴力匹配算法在每次失配时，都需要将指针移动到模式串的起始位置，最终的时间复杂度为 $O(|s1| * |s2|)$ 。而如果先求出模式串的前缀函数，再进行匹配，时间复杂度就会大大降低。如下图所示：

令指针 $i,j$ 分别指向主串和模式串，其中指针 $i$ 只可能向右，指针 $j$ 则需要在失配时回溯。
如果发生了失配，已知前后缀相同的最长长度 $next[j-1]$ ，那么指针 $j$ 可以直接回溯到下标 $next[j-1]$ ，也就是说跳过了模式串的前 $j$ 个字符的匹配过程。

代码模板

// 返回主串s1所有可行的匹配起始点
public List<Integer> strStr(String s1, String s2) {
    List<Integer> ans = new ArrayList<>();
    int n = s1.length(), m = s2.length();
    int[] next = new int[m];
    for(int i = 1;i < m;++i){
        int j = next[i-1];
        while(j != 0 && s2.charAt(i) != s2.charAt(j)) j = next[j-1];
        if(s2.charAt(i) == s2.charAt(j)) ++j;
        next[i] = j;
    }
    int j = 0;
    for(int i = 0;i < n;++i){
        while(j != 0 && s2.charAt(j) != s1.charAt(i)) j = next[j-1];
        if(s2.charAt(j) == s1.charAt(i)) ++j;
        if(j == m) {
            ans.add(i-m+1);
            j = next[j-1];
        }
    }
    return ans;
}

题目

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

3045. 统计前后缀下标对 II - 力扣（LeetCode）

Z函数(扩展KMP)

定义

对于一个长度为 $n$ 的字符串 $s$ ，定义函数 $z[i]$ 表示 $s[0,n-1]$ 和 $s[i,n-1]$ 的最长公共前缀的长度。特别地， $z[0]=0$ 。

以下样例展示了不同字符串的Z函数：

$z(aaaaa)=[0,4,3,2,1]$
$z(aaabaab)=[0,2,1,0,2,1,0]$
$z(abacaba)=[0,0,1,0,3,0,1]$

朴素算法

容易实现复杂度 $O(n^2)$ 的算法：

public int[] getZ(String s){
    int n = s.length();
    int[] z = new int[n];
    for(int i = 1;i < n;++i){
        while(i+z[i] < n && s.charAt(z[i]) == s.charAt(i+z[i])) ++z[i];
    }
    return z;
}

线性算法

从1到n-1依次计算 $z[i]$ 的值（ $z[0]=0$ ）。在计算 $z[i]$ 时，需要用到已经计算完成的 $z[0..i-1]$ 。
对于i，称区间 $[i, i+z[i]-1]$ 是 $i$ 的匹配段。在算法执行过程中，维护右端点最大的匹配段 $[l,r]$ 。由定义可知， $s[l,r]$ 与前缀 $s[0,r-l]$ 是相同的。初始时 $l=r=0$ 。

算法流程如下，计算 $z[i]$ 时：

若 $i <= r$ $i < = r$ ，由 $s[l,r]=s[0,r-l]$ $s [l, r] = s [0, r - l]$ 可得 $s[i,r]=s[i-l,r-l]$ $s [i, r] = s [i - l, r - l]$ 。因此 $z[i] >= min(z[i-l], r-i+1)$ $z [i] > = m i n (z [i - l], r - i + 1)$
- 若 $z[i-l]<r-i+1$ ，则 $z[i]$ 不可能超出 $s[i,r]$ 范围， $z[i]=z[i-l]$ 。
- 若 $z[i-l]>=r-i+1$ ，此时 $z[i]$ 超出了 $s[i,r]$ 范围，令 $z[i]=r-i+1$ ，然后暴力枚举直到 $z[i]$ 无法扩展为止。
若 $i > r$ ，直接按照朴素算法求出此时的 $z[i]$
求出 $z[i]$ 后，若新的右边界 $i+z[i]-1$ 大于 $r$ ，更新 $[l,r]$ ，即 $l=i,r=i+z[i]-1$

这个过程其实有点像manacher算法，都是维护了此前可达的最右侧边界，然后利用该边界提供的信息快速跳转到某个位置。可以访问这个网站来看 Z 函数的模拟过程。

代码模板

public int[] getZ(String s){
    int n = s.length();
    int[] z = new int[n];
    int l = 0, r = 0;
    for(int i = 1;i < n;++i){
        if(i <= r){
            if(z[i-l] < r-i+1) z[i] = z[i-l];
            else z[i] = r-i+1;
        }
        while(i+z[i] < n && s.charAt(i+z[i]) == s.charAt(z[i])) ++z[i];
        if(i+z[i]-1 > r){
            l = i;
            r = i+z[i]-1;
        }
    }
    return z;
}

时间复杂度： $O(n)$ ，由代码可知 $z$ 数组中每个位置最多被访问两次。

应用/题目

与前缀函数类似，Z函数可用于子串匹配问题，将原串 $s1$ 和模式串 $s2$ 拼接为 $s=s2+*+s1$ ，其中*为分割符。求出 $s$ 的Z函数后，对于 $[|s2|..|s|-1]$ 范围内的 $i$ ，若 $z[i]=|s2|$ ，则找到了一个匹配下标 $i$ 。参考代码如下：

public List<Integer> strStr(String s1, String s2) {
    List<Integer> ans = new ArrayList<>();
    String s = s2 + "*" + s1;
    int n = s1.length(), m = s2.length();
    int[] z = new int[n+m+1];
    int l = 0, r = 0;
    for(int i = 1;i < n+m+1;++i){
        if(i <= r){
            if(z[i-l] < r-i+1) z[i] = z[i-l];
            else z[i] = r-i+1;
        }
        while(i+z[i] < n+m+1 && s.charAt(i+z[i]) == s.charAt(z[i])) ++z[i];
        if(i+z[i]-1 > r){
            l = i;
            r = i+z[i]-1;
        }
        // 判断是否匹配
        if(i > m && z[i] == m) ans.add(i-m-1);
    }
    return ans;
}