本文共 2286 字，大约阅读时间需要 7 分钟。

题解 P5410 【【模板】扩展 KMP】

一、引言

一个算是冷门的算法（在竞赛上），不过其算法思想值得深究。

二、前置知识

三、经典扩展 KMP 模板问题

给你两个字符串 s 和 t，长度分别为 n 和 m。请输出 s 的每一个后缀与 t 的最长公共前缀。

示例说明

假设 S = "aaaaaaaaaabaa"，T = "aaaaaaaaaaa"，其中 n=13，m=11。

从图中可以看出：

• extend[1] = 10
• extend[2] = 9

通过分析发现，可以利用前缀函数的思想快速求解。

四、一般情况

设 extend[1...k] 已经计算完毕，并且在以前的匹配过程中在 S 中的最远位置是 p，即 p = max(i + extend[i] - 1)，其中 i = 1...k。

情况一：k + L < p

设 p0 是匹配的位置。

if (i + nxt[i - p0] < nxt[p0] + p0)
{
    // 第一种情况
    nxt[i] = nxt[i - p0];
}
else
{
    // 第二种情况
    now = max(now, 0);
    while (t[now] == s[i + now] && now < tlen)
    {
        now++;
    }
    nxt[i] = now;
    p0 = 0;
}

情况二：p ≤ k + L

if (i + nxt[i - p0] < nxt[p0] + p0)
{
    // 第一种情况
    nxt[i] = nxt[i - p0];
}
else
{
    // 第二种情况
    now = max(now, 0);
    while (t[now] == s[i + now] && now < tlen)
    {
        now++;
    }
    nxt[i] = now;
    p0 = 0;
}

五、求 nextnext

求 nextnext 的本质和求 extend 的本质一样，所以我们重新打一遍就好了。

KMP 算法思想

KMP 算法的思想是：将模式串与本体串都转换为前缀函数，然后利用前缀函数进行匹配，避免重复比较字符，从而提高效率。

时间复杂度

• 求 nextnext 的时间复杂度是 O(m)
• 求 extend 的时间复杂度是 O(n)
• 总时间复杂度是 O(n + m)，即 S 串与 T 串的长度之和。

六、代码

#include 
   
    
using namespace std;
int nxt[N], extend[N];
int slen, tlen;
char s[N], t[N];
void getnxt() {
    nxt[0] = tlen;
    int now = 0;
    while (t[now] == t[1 + now] && now < tlen) {
        now++;
    }
    for (int i = 1; i < tlen; ++i) {
        if (i + nxt[i - nxt[p0]] < nxt[p0] + p0) {
            nxt[i] = nxt[i - nxt[p0]];
        } else {
            now = max(now, 0);
            while (t[now] == s[i + now] && now < slen && now + i < tlen) {
                now++;
            }
            nxt[i] = now;
            p0 = 0;
        }
    }
}
void exkmp() {
    getnxt();
    int now = max(now, 0);
    while (s[now] == t[now] && now < min(slen, tlen)) {
        now++;
    }
    extend[0] = now;
    for (int i = 1; i < slen; ++i) {
        if (i + nxt[i - p0] < extend[p0] + p0) {
            extend[i] = nxt[i - nxt[p0]];
        } else {
            now = max(now, 0);
            while (t[now] == s[i + now] && now < tlen && now + i < tlen) {
                now++;
            }
            extend[i] = now;
            p0 = 0;
        }
    }
}
   

结论

通过以上方法，可以高效地解决扩展 KMP问题，快速找到 S 的每一个后缀与 T 的最长公共前缀。