扩展kmp

FJ_00460 · 2025-03-16 19:15:55 · 个人记录

扩展kmp(Z Algorithm)

引入

移除字符串的一部分，加上一部分，问多少步能变回原样(移除几个加上几个)

定义

是一种字符串算法。

核心：z数组

可以在O(n + m)的时间复杂度内，在给定的文本串T和一个模式串P中，找到所有匹配的位置。

Z函数

核心是z(i)

定义为：字符串s与s[i, ....... , n - 1]的最长公共前缀(LCP)

Z(i)是满足s[0, ....., x - 1]与s[i, ....., i + x - 1]

令Z(0) = 0

例子：

Z-box

这个过程就像啃老，老人死了就啃不了。
---------林老师

构建Z数组

通过维护一个窗口 Z-box ，利用已知信息高效计算Z函数

对于每个位置 $i

若 i 在已知的匹配区间内，即 i \le r ，则可以利用Z值的对称性来初始化 Z_i
否则，从位置 i 开始扩展，计算最长的公共前缀长度

快速求Z函数

若 z(i) \ne 0，可以定义区间[i, i + z[i] - 1]为一个Z-Box, 显然，Z-box 对应的子串一定是整个字符串的前缀
从左往右枚举下标i，同时维护l和r，用[l, r]表示满足 l \le i 且r最大的Z-Box。
综上，有3种情况，要分别考虑。

情况1 i > r

说明已经完全超过上一个Z-Box,任何一个新的Z-Box的r都会更大。
直接暴力比较，暴力计算出Z[i]
计算完成后，若Z(i) \ne 0 更新l和r。

当你做不了富二代，啃不了老，你就努力做个富一代，让别人啃你。 -------林老师

例

代码

if(i > r){
    while(i + z[i] < n && s[z[i]] == s[i + z[i]])
        z[i]++;
    l = i;
    r = i + z[i] - 1;
}

情况2 i \le r 且 z[i - l] < r - i + 1

已知s[0, ...., r - 1]与s[l, ....., r]相等，故s[i - l, ....., r - l]与s[i, ......, r]也相等。
所以，如果 Z[i - 1] < r - i + 1 ，说明从i开始匹配和从i - l开始匹配是一样的。
所以这个匹配一定会在离开Z-Box前停止
即Z[i] = Z[i - l]

else if(z[i - l] < r - i + 1)
    z[i] = z[i - l];

情况3 i \le r 且 z [i - l] \ge r - i + 1

说明整个Z-Box剩余部分都可以匹配，但后面的情况不确定，所以不能直接认定Z[i] = Z[i - 1]
但知道Z[i]至少有 r - i + 1，后面进行暴力扩展Z-Box尽量延长。

else{
        z[i] = r - i + 1;
        while(i + z[n] < n && s[z[i] == s[i + z[i]]])
            z[i] ++;
        l = i;
        r = i + z[i] - 1;
    }

其实

情况1和3可以合并

for(int i = 1, l = 0, r = 0; i < n; i ++){
    if(z[i - l] < r - i + 1)
        z[i] = z[i - l];
    else{
        z[i] = max(r - i + 1, 0);
        while(i + z[i] < n && s[z[i] == s[i + z[i]]])
            z[i] ++;
        l = i;
        r = i + z[i] - 1;
    }
}

复杂度是O(n)，因为内层循环每执行一次，都会使r加1，执行次数不会超过n次。