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

· · 算法·理论

理论部分

Border、回文前缀的等差性

Border 的等差性

首先我们看一点东西:

比如 abbabbaborder \ 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 的分析方法,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 11 不需要 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;

不难发现这样复杂度是均摊的,有点难受。如何像 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)

Q: $ 我们跳链是为了找左边有一个字符 $c$ 的回文子串,但是左边有什么跟这个串本身又没有关系,而是跟 $s$ 相关,如何保证记下来的 $get$ 是通用的? $\\ 对 $get$ 数组做可持久化就得到了可持久化 PAM。 --- # 例题 为了更好地理解这部分知识点,我会把独属于每个题的分析问题性质部分(称 A 部分)和上文提到的通用的字符串知识点和优化部分(称 B 部分)拆开,最后还会给出具体的细节实现(称 C 部分)。 ## P1393(容斥 DP + $O(\log)$ 段等差 $border$) > 求 $n \ (\leq 2 \times 10^5)$ 长度随机生成的字符串包含给定字符串 $s$ 的概率。 ### Part A 令 $f_i$ 表示 $[i - |s| + 1, i]$ 这些字符恰好是 $s$,且前面从来没有出现 $s$ 的方案数,不难容斥做到 $O(n^2)$。 ### Part B 你把代码写出来就能知道,刚刚容斥的瓶颈是枚举 $border$,但是它们构成了 $O(\log |s|)$ 个等差数列,因此记 $O(\log |s|)$ 份前缀和就能优化了。 ### Part C ```cpp /* Good Game, Well Play. */ #include <bits/stdc++.h> #define lowbit(x) ((x) & (-(x))) using namespace std; const int N = 200010, mod = 998244353; inline long long qpow(long long a, long long b) {long long res = 1; while(b) {if(b & 1) res = res * a % mod; b >>= 1, a = a * a % mod;} return res;} int n, k, m, s[N], nxt[N], w[N], wn; long long f[N], pw[N], pwi[N]; inline void get(int len) {if(!len) return ; w[++wn] = m - len, get(nxt[len]);} long long p[110][N]; struct Seq {int x, d, lim;} seq[110]; int sn; inline long long S(int id, int l, int r) {if(r <= 0) return 0; l = max(l, 0); return (p[id][r] - p[id][l] + mod) % mod;} int main() { // freopen("text.in", "r", stdin); // freopen("prog.out", "w", stdout); ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n >> k >> m; for(int i = 1; i <= m; ++i) cin >> s[i]; pw[0] = 1; for(int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * k % mod; pwi[0] = 1; for(int i = 1, iv = qpow(k, mod - 2); i <= n; ++i) pwi[i] = pwi[i - 1] * iv % mod; for(int i = 2; i <= m; ++i) { nxt[i] = nxt[i - 1]; while(nxt[i] && s[nxt[i] + 1] != s[i]) nxt[i] = nxt[nxt[i]]; if(s[nxt[i] + 1] == s[i]) ++nxt[i]; } get(nxt[m]); for(int l = 1; l <= wn; ++l) { int r = l + 1; if(l == wn) seq[++sn] = {w[l], 1, 0}; else { while(r < wn && w[r + 1] - w[r] == w[r] - w[r - 1]) ++r; seq[++sn] = {w[l], w[l + 1] - w[l], r - l}; l = r; } } for(int i = m; i <= n; ++i) { f[i] = pw[i - m]; f[i] = (f[i] - p[0][i - m] * pw[i - m] % mod + mod) % mod; for(int j = 1; j <= sn; ++j) f[i] = (f[i] - S(j, i - seq[j].x - seq[j].d * (seq[j].lim + 1), i - seq[j].x) + mod) % mod; p[0][i] = (p[0][i - 1] + f[i] * pwi[i]) % mod; for(int j = 1; j <= sn; ++j) p[j][i] = (p[j][max(0, i - seq[j].d)] + f[i]) % mod; } long long res = 0; for(int i = m; i <= n; ++i) res = (res + f[i] * pw[n - i]) % mod; cout << res * qpow(pwi[1], n) % mod << '\n'; return 0; } /* */ ``` ## P5287(Ad-hoc + $O(\log)$ 段等差 $border$) > 写一个程序,要求支持加入 $x$ 个相同字符以及回退版本,并在每次操作后求出 $\sum nxt$。不要求可持久化,允许离线。 ### Part A 因为不要求可持久化,所以回退版本并不是什么难点,建出操作树或者直接暴力删都是可以的。问题在于如何维护加字符操作。我们知道若两串字符相等,除了首尾两部分,把剩下的二元组 $(x, c)$ 看成单个**压缩字符**,它们组成的字符串应该也是完全相等的。不妨对压缩字符做 KMP。边跳 $nxt$ 边计算贡献。 计算贡献的部分可以参考我的代码, ### Part B 回滚 ban 掉了均摊复杂度,算贡献 ban 掉了 KMP 自动机,但是我们还有一条路,即运用 $O(\log)$ 段等差数列性质。 这个性质的由来是字符串的周期,那么一段等差 $border$ 对应的前缀后面接的字符串都有一段 LCP,即这个周期。周期至少有一个压缩字符,则它们对答案的贡献一致,可以直接跳过,跳到大于周期 $t$ 的最小 $border$。 这样暴力跳 $nxt$ 的复杂度变为严格 $O(\log n)$,可以通过。 ### Part C 加了注释。 ```cpp /* Good Game, Well Play. */ #include <bits/stdc++.h> #define lowbit(x) ((x) & (-(x))) using namespace std; const int N = 100010, mod = 998244353; int n, ver[N]; long long res[N]; struct Edge {int to, x; char c;}; vector < Edge > tr[N]; int idx = 1; struct Char {int x, c;} s[N]; int len, prx[N], nxt[N]; inline bool find_son(int p, int x, int c) { if(!p) return (s[p + 1].c == c && s[p + 1].x <= x); // 如果在字符串的开头,那么开头少几个字符也是可以匹配上的,只要 x 个字符不全用完就行了 else return (s[p + 1].c == c && s[p + 1].x == x); // 不然必须要求 (x, c) 二元组相等 } inline int get_sum(int l, int r) {if(l > r) return 0; return 1ll * (l + r) * (r - l + 1) / 2 % mod;} inline int insert(int x, char c) { s[++len] = {x, c}; prx[len] = prx[len - 1] + s[len].x; if(len == 1) return get_sum(1, x - 1); // 同 KMP 和 Z 函数理,len = 1 需要特判 int p = nxt[len - 1], lst = len, maxlen = 0; long long delt = 0; // 这里记录 maxlen 的意思是,当前有 x 个字符等着算贡献,因为要找最大 border,所以贪心把前面能找的都找了,后面的以后再去找 while(p && !find_son(p, x, c)) { if(s[p + 1].c == c && min(x, s[p + 1].x) > maxlen) { delt = (delt + get_sum(prx[p] + maxlen + 1, prx[p] + min(x, s[p + 1].x))); maxlen = s[p + 1].x; } if(lst - p == p - nxt[p]) { int t = p - nxt[p]; lst = p; p = p % t + t; } else lst = p, p = nxt[p]; } if(find_son(p, x, c)) { nxt[len] = p + 1; delt = (delt + get_sum(prx[p] + maxlen + 1, prx[p] + s[p + 1].x)); delt = (delt + 1ll * s[p + 1].x * (x - max(maxlen, s[p + 1].x))); // 这是针对匹配到开头,x 个字符不全用完所补加的贡献 } else { nxt[len] = p; if(s[p + 1].c == c && min(s[p + 1].x, x) > maxlen) delt = (delt + get_sum(maxlen + 1, maxlen + min(s[p + 1].x, x))); } return delt; } inline void roll() { s[len] = {0, 0}; prx[len] = nxt[len] = 0; --len; } inline void solve(int now) { for(Edge li : tr[now]) { res[li.to] = (res[now] + insert(li.x, li.c)) % mod; solve(li.to); roll(); } } int main() { // freopen("text.in", "r", stdin); // freopen("prog.out", "w", stdout); ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n; ver[0] = 1; for(int i = 1, p = 1; i <= n; ++i) { int op, x; char c; cin >> op; if(op == 1) { cin >> x >> c; ++idx; tr[p].push_back({idx, x, c}); p = idx; ver[i] = p; } else { cin >> x; ver[i] = p = ver[x]; } } solve(1); for(int i = 1; i <= n; ++i) cout << res[ver[i]] << '\n'; return 0; } /* */ ``` ## P4156(同余最短路 + $O(\log)$ 段等差 $border$) > 给定一个字符串 $s$,你有一个串 $t$,初始为空,可以反复做以下操作: > > - 在 $t$ 后面接上一段长度不超过 $|s|$ 的字符,使得 $t$ 的最后 $|s|$ 个字符等于 $s$。 > > 求 $t$ 的**长度**在 $m$ 范围内的可能数量,$m \leq 10^{18}$。 ### Part A 可见扩展一次的长度总是 $|s| - k$,其中 $k$ 是某个 $border$ 的长度。 则所求的是值域为 $m$,元素个数 $O(|s|)$ 个的可行性完全背包。稍微优化一下,同余最短路也是做这个问题的。 ### Part B 运用关键性质:$O(n)$ 个元素实际上构成了 $O(\log n)$ 段等差数列,因此对每段等差数列 $x, x + t, x + 2t, \dots, x + yt$ 分别算同余最短路,中间涉及到每次更新和更换模数两个问题。 以上面的 $x$ 作为模数,则所有 $p \to (p + t) \bmod x$ 的边构成若干个环,环内的 $p$ 可以在不超过走 $y$ 次 $p \to (p + t) \bmod x$ 的边的情况下更新所达到的点,可以单调队列维护。 更换模数时,设当前模数是 $x$,上次是 $x'$,首先得做一个 $p \to f_p \bmod x$,然后还要 $p \to (p + x') \bmod x$,此时没有最多 $y$ 次的限制,不需要单调队列了。 ### Part C 实现难度主要在于同余最短路,建议先学习 P3403 模板题,会了那个题的思想后写起来很快。 ```cpp /* Good Game, Well Play. */ #include <bits/stdc++.h> #define lowbit(x) ((x) & (-(x))) using namespace std; const int N = 500010; int T, n, nxt[N], w[N], wn; long long m; string s; inline void get(int len) {w[++wn] = n - len; if(len) get(nxt[len]);} struct Data {int id; long long num;}; deque < Data > dq; long long f[N], tmp[N]; int lst; bool vis[N]; inline void refresh(int mod, int d, int lim) { // cerr << "refresh " << mod << " " << d << " " << lim << '\n'; if(lst == 0) { for(int i = 0; i < mod; ++i) f[i] = m + 1; f[n % mod] = n; } else { for(int i = 0; i < mod; ++i) tmp[i] = m + 1; for(int i = 0; i < lst; ++i) tmp[f[i] % mod] = min(tmp[f[i] % mod], f[i]); for(int i = 0; i < mod; ++i) vis[i] = false; for(int i = 0; i < mod; ++i) { if(vis[i]) continue; int p = i, mnp = -1; long long comp = m + 10; vector < int > rec; do {if(tmp[p] < comp) comp = tmp[p], mnp = p; p = (p + lst) % mod;} while(p != i); p = mnp; while(!vis[p]) {vis[p] = true; rec.push_back(p); p = (p + lst) % mod;} comp = m + 10; for(int j = 1; j < rec.size(); ++j) tmp[rec[j]] = min(tmp[rec[j]], tmp[rec[j - 1]] + lst); } for(int i = 0; i < mod; ++i) f[i] = tmp[i]; } // cerr << "current f : "; for(int i = 0; i < mod; ++i) cerr << f[i] << " "; cerr << '\n'; lst = mod; for(int i = 0; i < mod; ++i) vis[i] = false; for(int i = 0; i < mod; ++i) { if(vis[i]) continue; int p = i, mnp = -1; long long comp = m + 10; vector < int > rec; do {if(f[p] < comp) comp = f[p], mnp = p; p = (p + d) % mod;} while(p != i); p = mnp; while(!vis[p]) {vis[p] = true; rec.push_back(p); p = (p + d) % mod;} dq.clear(); dq.push_back({0, f[rec[0]]}); for(int j = 1; j < rec.size(); ++j) { while(!dq.empty() && j - dq.front().id > lim) dq.pop_front(); f[rec[j]] = min(f[rec[j]], dq.front().num + j * d + mod); Data cur = {j, f[rec[j]] - j * d}; while(!dq.empty() && dq.back().num >= cur.num) dq.pop_back(); dq.push_back(cur); } } // cerr << "final f : "; for(int i = 0; i < mod; ++i) cerr << f[i] << " "; cerr << '\n'; } inline void sol() { cin >> n >> m; lst = 0; cin >> s; s = ' ' + s; for(int i = 2; i <= n; ++i) { nxt[i] = nxt[i - 1]; while(nxt[i] && s[nxt[i] + 1] != s[i]) nxt[i] = nxt[nxt[i]]; if(s[nxt[i] + 1] == s[i]) ++nxt[i]; } wn = 0; get(nxt[n]); // cerr << "w : "; for(int i = 1; i <= wn; ++i) cerr << w[i] << " "; cerr << '\n'; for(int l = 1; l <= wn; ++l) { int r = l + 1; if(l == wn) refresh(w[l], 0, 0); else { while(r < wn && w[r + 1] - w[r] == w[r] - w[r - 1]) ++r; refresh(w[l], w[l + 1] - w[l], r - l); l = r; } } long long res = 0; for(int i = 0; i < lst; ++i) if(f[i] <= m) res += 1 + (m - f[i]) / lst; cout << res << '\n'; } int main() { // freopen("text.in", "r", stdin); // freopen("prog.out", "w", stdout); ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> T; while(T--) sol(); return 0; } /* */ ``` ## P5555(PAM) ### Part A 无。 ### Part B 走相同的转移边得到的回文串是一样的,可以同时在两个 PAM 上 DFS。 ### Part C DFS 部分: ```cpp int res, cnt; inline void search(int x, int y) { if(!x || !y) return ; if(pam[0].len[x] > res) res = pam[0].len[x], cnt = 0; if(pam[0].len[x] == res) ++cnt; for(int i = 1; i <= 26; ++i) search(pam[0].son[x][i], pam[1].son[y][i]); } ``` ## CF932G(DP + PAM + $O(\log)$ 段回文) > 求把 $s$ 划分成若干段的方案数,满足若段数为 $k$,总有 $s'_i = s'_{k - i + 1}$。 ### Part A 设原字符串为 $\overline{s_1 s_2 \dots s_n}$,把它变为 $\overline{s_1 s_n s_2 s_{n - 1} \dots s_{\frac{n}{2} + 1}}$,则原问题变为划分为若干偶数回文段的方案数。 ### Part B 这部分是必须掌握的经典问题,详见 [OI Wiki 相关部分](https://oi-wiki.org/string/pam/#%E4%BC%98%E5%8C%96)。 给点补充: $Q_1 :$ $f, g$ 数组是依托什么设定的?$g$ 是 DP 数组吗?影响 $g$ 的是 $i$ 的变化还是 PAM 中的跳指针?$\\ $Q_2 :$ 既然 $g$ 数组的下标对应的是 PAM,那么它为什么可以精准地贡献到 $f_i$ 上?$\\ ### Part C 提示:如果调试不出来,先考虑是 PAM 写错了,然后再看 DP 过程。 和这个题相似的还有 CF906E,基本上是双倍经验,能默写出其中一道题的代码就都能轻松通过。 加注释的代码。 ```cpp /* Good Game, Well Play. */ #include <bits/stdc++.h> #define lowbit(x) ((x) & (-(x))) using namespace std; const int N = 1000010, mod = 1e9 + 7; int n; string s, org; struct PAM { int son[N][27], tr[N][27], fail[N], len[N], dif[N], slink[N], idx, p; inline void init() {p = idx = 2; fail[2] = 1; len[1] = -1, len[2] = 0;} inline void insert(int pos, char c) // 这里采用的是严格 O(字符集大小) 的 PAM 实现,也可以用均摊 O(1) 的实现。 { if(pos - len[p] - 1 <= 0 || s[pos - len[p] - 1] != c) p = max(1, tr[p][c - 'a' + 1]); if(!son[p][c - 'a' + 1]) { fail[++idx] = max(2, son[max(1, tr[p][c - 'a' + 1])][c - 'a' + 1]); len[idx] = len[p] + 2, dif[idx] = len[idx] - len[fail[idx]]; if(dif[idx] == dif[fail[idx]]) slink[idx] = slink[fail[idx]]; // slink 指向上一个等差数列的最后一项 else slink[idx] = fail[idx]; son[p][c - 'a' + 1] = idx; memcpy(tr[idx], tr[fail[idx]], sizeof(tr[idx])); tr[idx][s[pos - len[fail[idx]]] - 'a' + 1] = fail[idx]; } p = son[p][c - 'a' + 1]; } }; PAM pam; long long f[N], g[N]; int main() { // freopen("text.in", "r", stdin); // freopen("prog.out", "w", stdout); ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> org; n = org.length(); org = ' ' + org; s = " "; for(int i = 1; i <= n / 2; ++i) s += org[i], s += org[n - i + 1]; if(n % 2 == 1) {cout << 0 << '\n'; return 0;} pam.init(); f[0] = 1; for(int i = 1; i <= n; ++i) { pam.insert(i, s[i]); for(int pt = pam.p; pt >= 3; pt = pam.slink[pt]) { g[pt] = f[i - pam.len[pam.slink[pt]] - pam.dif[pt]]; // 这是 g[pt] 和 g[fail[pt]] 之间的差值,OI Wiki 中已说明 if(pam.slink[pt] != pam.fail[pt]) // 注意判断 fail 树上的父亲与自己不在同一个等差数列的情况 g[pt] = (g[pt] + g[pam.fail[pt]]) % mod; if(i % 2 == 0) f[i] = (f[i] + g[pt]) % mod; // 由于必须划分为偶回文串,因此 i 是 2 的倍数是转移 } } cout << f[n] << '\n'; return 0; } /* */ ``` ## QOJ5037(线段树 + $O(\log)$ 段回文) > 在支持单点修改字符的情况下求给定字符串 $s$ 的一个子串 $s_{[l, r]}$ 的回文后缀数量,强制在线。 很有操作的一道题。设 $X$ 的 $k$ 次方表示字符串 $X$ 重复 $k$ 次得到的结果,$X'$ 表示 $X$ 翻转得到的字符串。特别的,$X^0$ 为空串。 ### Part A 这个题带修带查,还强制在线,显然不能 PAM 做了。但是无论字符串如何变化,$O(\log |s|)$ 段回文的性质都是在的,不妨像动态 DP 一样,把字符串挂到线段树上面,并维护 $[l, r]$ 的回文前缀和后缀。因为等差性,要记录的信息是 $O(\log(r - l + 1))$ 量级的。 ### Part B 既然维护回文前缀和后缀是同一个方式,我们只分析维护后缀的方法。现已知线段树上 $[l, mid], (mid, r]$ 节点的回文前后缀,尝试得到 $[l, r]$ 的回文后缀信息。 这里免不了分类讨论: #### Case I 回文后缀在 $(mid, r]$ 中 这部分可以继承 $(mid, r]$ 节点的信息,他们显然是等价的。 #### Case II 回文后缀跨过 $mid$,且中线在 $(mid, r]

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

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

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

A, AB, AB^2, AB^3, \dots, AB^k

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

如果 $C$ 不是 $B$ 的前缀,那最多也就一个 $(B^xC)'AB^kC$ 是合法的。把它找出来就可以了。 如果 $C$ 是 $B$ 的前缀,那 $x$ 越小越容易合法,二分查找边界。 #### Case III 中线在 $mid$ 和 $mid + 1$ 之间 这种情况只对应一个后缀,判断它是不是回文的就行了。 #### Case IV 中线在 $[l, mid]

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

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

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

Part C

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

代码直接找 QOJ 提交记录。