[字符串] Border 和回文前后缀的性质、维护和运用

Felix72 · 2025-01-18 15:37:18 · 算法·理论

理论部分

Border、回文前缀的等差性

Border 的等差性

首先我们看一点东西：

• 若字符串 s 有 border 长度为 k 且 2k > s，则 |s| - k 是 s 的一个周期。

比如 abbabba 有 border \ k = 4，则 7 - 4 = 3 是其的一个周期。这个性质应该比较容易理解。同理，知道周期也就能推导出对应的 border。

那么就有一个神奇的性质：对于一个最大 border \ k_1 和一个大于长度一般的周期 k_2，因为 |s| - k_1, |s| - k_2 都是周期，|s| - k_1 是最小周期，而由弱周期引理，他们的 \gcd 还是周期，因此 |s| - k_2 只能是最小周期的倍数了。换句话说，令 t 为最小周期，满足 2k > |s| 的 border 必有 k' = k_{max} - xt，它们构成一段等差数列。

那么对一半长度以内的 border 做同样的递归分析，可知所有 border 划分成 O(\log) 段等差数列。

回文前后缀的等差性

对着回文串的回文前缀分析，可以得到类似的结果。

这个并不难理解，还是考虑 2k > |s| 的最大和次大的回文前缀 k_1, k_2，我们设 t = k_1 - k_2，令 [k_2 + 1, k_1] 是一个模板段，可知模板段在 [1, t] 倒着出现，又因为 k_2 是回文，所以模板段在 [k_2 - t + 1, k_2] 出现。又由此可知，模板段在 [t + 1, 2t] 倒着出现，等等。只要不越过中线，模板段就会像这样反复出现，这和 border 与周期的关系就很类似了。

当然你也可以直接证明它：

• 一个回文串的回文前缀等价于其 border。

这个引理很容易理解，那这样的话按照 border 的分析方法，O(\log) 段等差数列的性质就不证自明了。

KMP 自动机

往往我们写 KMP 和 AC 自动机时，用的是均摊 O(1) 的写法，这种写法遇到可持久化等要求时可能退化。

但是有对应的调整方法。具体地，不再设 son_{p, c} 表示 p 节点连出字符 c 的边指向的儿子，而是令 tr_{p, c} 表示从 p 开始要走 c 边转移，通过一系列跳 fail 后再走 c 边达到的节点。

实现也相当简单：

if(son[p][c]) tr[p][c] = son[p][c];
else tr[p][c] = tr[fail[p]][c];

看起来只是换了种写法实现，实际上有本质不同：这样复杂度由均摊 O(1) 变为严格 O(\sum)。你会发现这样就能支持一个版本扩展出多个版本，以及做 AC 自动机上 DP。

（其实 KMP 自动机可以视作单个串的 AC 自动机。）

回文自动机

又称回文树，看着和 KMP/AC 自动机比较像，只不过是维护回文子串的。

首先我们明确，回文子串肯定可以在不损失信息的情况下以 O(n) 状态数维护，因为一个字符串每增加一个字符，其本质不同回文子串最多增加 1 个。这是回文自动机能存在的原因。

它的思想也和 KMP/AC 自动机比较类似。首先我们为偶回文和奇回文设置两个根节点 0, 1，并建边 0 \to 1。1 不需要 fail 指针，因为单个字符也是回文，它不会失配。剩下的就和 KMP 的加入一样了。加入一个新字符 s_p 时，指针指向的是以 p - 1 结尾的最长回文串对应的节点，此时如果这个回文串前后的字符一致，那么直接扩展，否则就跳 fail 指针直到可以扩展为止。

当然只是说说原理是过不了题的，下面是一个回文自动机的简单封装实现和一些常见问题解答：

int n, res[N]; string s;
struct PAM
{
    int fail[N], idx, dep[N], p, len[N], tr[N][27];

    inline void init()
    {
        idx = 2; fail[2] = fail[1] = 1; p = 2;
        len[1] = -1; len[2] = 0;
    }
    inline int insert(int pos, char c)
    {
        while(p != 1 && (pos - len[p] - 1 <= 0 || s[pos - len[p] - 1] != c)) p = fail[p];
        if(!tr[p][c - 'a' + 1])
        {
            int ps = fail[p];
            while(ps != 1 && (pos - len[ps] - 1 <= 0 || s[pos - len[ps] - 1] != c)) ps = fail[ps];
            fail[++idx] = max(2, tr[ps][c - 'a' + 1]);
            tr[p][c - 'a' + 1] = idx;
            len[idx] = len[p] + 2, dep[idx] = dep[fail[idx]] + 1;
        }
        p = tr[p][c - 'a' + 1];
        return dep[p];
    }
}; PAM pam;

• Q_1:$ 这个预处理的 $1$ 和 $2$ 是什么节点？$len_1 = -1, len_2 = 0$ 有什么意义？$\\
• Q_2:$ 这个建造过程的复杂度是多少？$\\
• Q_3:$ ```fail[++idx] = max(2, tr[ps][c - 'a' + 1]);``` 这句话中，对 $2$ 取 $\max$ 是什么意思？$\\

不难发现这样复杂度是均摊的，有点难受。如何像 KMP 自动机一样优化使得 均摊 O(1) \to 严格 O(\sum) 呢？

有的兄弟，有的，像这样的方法有整整 2 种。

非均摊优化方向 A

我们思考等差数列性质的本质，就是周期。既然是周期，那么应该有相当多的 border 在跳链时，其左边的字符是一样的，也就是 (pos - len[ps] - 1 <= 0 || s[pos - len[ps] - 1] != c) 这个语句返回的结果相同，这样算下来只用跳 O(\log |s|) 次就能找到想要的节点了。

非均摊优化方向 B

这个优化方向相对更有价值一些，甚至还能可持久化。

我们把 insert 函数改成这样：

inline int insert(int pos, char c)
{
    if(pos - len[p] - 1 <= 0 || s[pos - len[p] - 1] != c) p = max(1, get[p][c - 'a' + 1]);
    if(!tr[p][c - 'a' + 1])
    {
        int ps = max(1, get[p][c - 'a' + 1]);
        fail[++idx] = max(2, tr[ps][c - 'a' + 1]);
        tr[p][c - 'a' + 1] = idx;
        len[idx] = len[p] + 2, dep[idx] = dep[fail[idx]] + 1;
        memcpy(get[idx], get[fail[idx]], sizeof(get[idx]));
        get[idx][s[pos - len[fail[idx]]] - 'a' + 1] = fail[idx];
    }
    p = tr[p][c - 'a' + 1];
    return dep[p];
}

你发现跳链的过程被一个叫做 get 的数组替换了。

这个数组相当于记忆化搜索，当我们要从 p 节点为了找 c 字符时开始跳，这个结果可以记作 get_{p, c}。每次新建节点 p 时，从 fail 树上的父亲继承 get 数组，然后用 p \to fail_p 更新 get_p 即可。这样我们用类似 DP 的方式存下了跳链的结果，也就变成了 O(\sum) - O(1)。

比如 aaab|cdcb （l = 1, mid = 4, r = 8, | 是分割线，不是字符），后缀 bcdcb 就是我们讨论的情况。

此时这个后缀必定形如 [l, mid] 的后缀 + (mid, r] 的一段回文前缀 + (mid, r] 剩下的部分。

这个 (mid, r] 的回文前缀看起来就像突破口，我们知道它由 O(\log) 段等差数列组成，拿出其中一段等差数列分析，这些字符串形如这样：

则我们要找的后缀长这样：DAB^kC。其中 B 不能是 C 的前缀，否则这个 k 次方还能更大。

不难发现，这些后缀是 [l, mid] 的回文后缀通过向两边扩展形成的。

还是只看其中一个等差数列 A, BA, B^2A, \dots, B^kA。假设现在往后面加一个字符串 C，分析哪些串可以在前面加一个相同的字符串满足仍然是回文的。

我们仿照 Case II，如果 C 有周期 B（|C| 不一定是 |B| 的倍数），那么对于一个 B^xA，x 越小越容易合法，如果没有周期 B，那么最多只会有一个串。

Part C

刚刚大量的分析都要用到字符串判等。线段树维护哈希？确实可以，但是又白给一只 \log。可以用分块 O(1) 查询哈希值。

代码直接找 QOJ 提交记录。