kmp & Border 相关

写在前面

一直想写一个 Border 相关的文章。

网上 kmp 相关的文章都好唐啊，全是半懂不懂的人在随机说话。符号系统混乱，逻辑错误百出，还没有任何深刻的理解。

忍不了一点。

感觉越基础的算法越难自学，因为网络上基础算法的 blog 质量都比较差。高水平选手不屑于写这些基础算法的 blog，而低水平选手写出来的 blog 往往质量很差。

记号 & 约定

• 的长度为

• 为 的第 个字符

• 为由 的第 个字符到第 个字符组成的字串。

• 称为 的长为 的前缀，简写为 。 在意义明确的情况下，可简写为

• 称为 的长为 的后缀，简写为 或

定义和简单性质

对于字符串 ，若 满足 与 相等，则称 为 的一个长为 的 。显然 是极大的 ，不过她实在太平凡了，下面我们讨论的都是除去她的“真 ”

记 的集合 。

一个重要的性质：

的 还是 。

取 ，不妨设 。

记 ，。

由于 ，则 为 的前缀，即 为 的前缀。

同理， 为 的后缀，即 为 的后缀。

综上， 既是 的前缀，又是 的后缀，即 为 的一个 ，。

预处理

考虑如何求出 的所有 。

不妨设 为 中的极大元。

则对 且 ， 都是 的 。

注意到，我们把现在把求 的 转化为了求 的长度为 的前缀的 。

对于每一个前缀，如果我们都知道她的 函数值，获得所有的 将是轻松的。

考虑增量构建。显然 。

设已知 的值，新加入的字符 为 。

那么相较于 ， 中的每个后缀都增加了 。因此如果 的一个长为 的 满足 ，则 也是 的 。

那么一个 trivial 的实现方法就是暴力遍历 的所有 ，然后找到满足上述条件的最大 ，此时有 。

同时，按照每次取出 中的极大元的方法遍历的 是从大到小的，第一次遍历的到合法的 就恰好是 的值。

复杂度分析

考虑一个势能函数 ，当前尝试匹配的位置。

匹配上合法的一个 能够使得 变大 ，称这种操作为 操作。

不能够匹配合法的 会使得 变小，称这种操作为 操作。

显然在全过程中 始终非负，因而 , 即使 变小的总次数不超过使 变大 的次数。

又因为每次操作都为 ，, 所以 。

代码实现

inline std::vector<int> get_pi(const std::string &s) {
    std::vector<int> pi(s.length());

    rep (i, 2, (int) s.length() - 1) {
        int j = pi[i - 1];
        while (j and s[j + 1] != s[i]) j = pi[j];
        if (s[j + 1] == s[i]) j++;
        pi[i] = j;
    }

    return pi;
}

* 的结构

前文提到，

的 还是 。

这样的性质使得 的结构是树状的。在算法竞赛中，这棵树被称作 树。

具体地，连边 。在这样得到的结构中，从 到根 的路径恰好为 的所有 。

这启示我们和 相关的统计可以转化为树上路径统计。