题解 P3375 【【模板】KMP字符串匹配】

一扶苏一 · 2019-09-04 03:56:35 · 题解

Algorithm

Task

给定一个文本串 S 和一个模式串 T，求 T 在 S 中出现的所有位置。

Limitations

要求时空复杂度均为线性。

Solution

回头重新学一遍看毛片 KMP 算法。

设 X 是一个字符串，则以下表述中，X_u 代表 X 的第 u 个字符，X_{u \sim v} 代表 X 的从 u 起到 v 结束的字串。

首先定义一个字符串的公共前后缀为这个字符串的一个 border，最长公共前后缀称为最长 border。特别的，不认为字符串本身是自身的 border。

性质：字符串 S 的 border 的 border 一定是 S 的 border，正确性显然。因此不断地跳最长 border 可以遍历字符串的所有 border

例如，对于字符串 abaab 来说，其唯一的 border 是 ab。

暴力匹配两个字符串，时间复杂度为 O(|S||T|)，考虑优化这个算法。

假设当前匹配时 S 扫描到了第 i 位， T 扫描到了第 j 位，且 S 从 i 向前 j 位组成的字符串与 T 的前 j 位相同，而 S_{i + 1} \neq T_{j+1}，我们称为发生了失配。

考虑失配时，指针 i 不变，只有将指针 j 前移，才可能令下一位成功匹配。由于 i 不变，所以下一个可能发生匹配的字符串一定是 T_{1 \sim j} 的某个前缀 T_{1 \sim k} 满足

其中由于 T_{1 \sim k} 是 T_{1 \sim j} 的字串，一定有 k < j。由于 S_{1 \sim i} 的后 j 位与 T 的前 j 位匹配，又有 k < j，因此 T_{1 \sim j} 的后 k 位一定与 S_{1 \sim i} 的后 k 位即 S_{i - k + 1 \sim i} 匹配。得出

上面两个式子等量代换得到

由 border 的定义，我们发现 T_{1 \sim k} 一定是 T_{1 \sim j} 的 border。根据 border 的性质，我们只需要不断的跳 T_{1 \sim j} 的最长 border 即可找到一个最长的可以与 S_{1 \sim i} 的后几位匹配的字串。因此问题转化为了如何求一个字符串 T 的所有前缀的最长 border。

显然 border_1 = 0。从第 2 位开始，我们发现问题等价于用 T（模式串） 的一个前缀去匹配 T_{1 \sim i} （文本串）的一个后缀，求这个后缀最长是多少，而这个问题的解决方法与上面那个问题的方法 完 全 一 致，都是不断跳 border 即可。在 i 与 j 成功匹配时，记录 border_i = j。而在这个问题中，由于 j 恒小于 i，正向扫描 i 时，所用到的 border 值都已经被计算出，因此可以得出正确的结果。

考虑时间复杂度：一个显然的事实是每次跳 border 模式串指针 j 都会至少减少 1，而当且仅当第 S_{i+1} 与第 T_{j+1} 匹配时，j 才会自增，因此 j 仅增加了 O(|S|)，因此 j 只可能减少 O(|S|) 次，所以跳 border 的总次数不超过 O(|S|)，而扫描整个文本串需要 O(|S|) 的时间，因此总时间复杂度 O(|S|)。

Example

P3375 【模板】KMP字符串匹配

Description

给定一个文本串 S 和一个模式串 T，求 T 在 S 中出现的所有位置，同时要求输出 T 的每个前缀的 border 长度。

Limitations

字符串长度不超过 10^6

Solution

板板题

Code

#include <cstdio>
#include <cstring>

const int maxn = 1000006;

char S[maxn], T[maxn];
int nxt[maxn];

void KMP(char *A, char *B, int x, int y, const bool pt);

int main() {
  freopen("1.in", "r", stdin);
  scanf("%s\n%s", S + 1, T + 1);
  int x = strlen(S + 1), y = strlen(T + 1);
  KMP(T, T, y, y, false); KMP(S, T, x, y, true);
  for (int i = 1; i <= y; ++i) {
    qw(nxt[i], i == y ? '\n' : ' ', true);
  }
  return 0;
}

void KMP(char *A, char *B, int x, int y, const bool pt) {
  for (int j = 0, i = pt ? 1 : 2; i <= x; ++i) {
    while (j && (B[j+1] != A[i])) j = nxt[j];
    if (B[j+1] == A[i]) ++j;
    if (!pt) nxt[i] = j;
    if (j == y) {
      qw(i - y + 1, '\n', true);
    }
  }
}