字符串（KMP & exKMP & AC 自动机 & Manacher & 回文自动机） 笔记

KMP

P3375 【模板】KMP。

要求：

• $s_2$ 匹配上 $s_1$ 时，匹配上的第一个字母位于 $s_1$ 的位置（如 $s_1=\mathtt{\text{abababa}}$，$s_2=\mathtt{\text{aba}}$，答案即为 $1$，$3$，$5$）。

• $s_2$ 每个前缀的 border。

1. 定义

Border：一个字符串最长的相同的前缀和后缀的长度。

文本串：被别人匹配的串，$s_1$。

模式串：匹配别人的串，$s_2$。

2. 理解

为方便表述，下文默认字符串从 $1$ 而不是从 $0$ 开始。

---------j
s2: abcabc
s1: abcabab
---------i

如图（?），当匹配到这种情况是，暴力的方案是把 $j$ 重新移回 $1$ 的位置，但显然，可以这样：

---------j
s2: ---abcabc
s1: abcabab
---------i

所以，$km{p}_j$ 就是找模式串 $j$ 这一位失配后，$j$ 应该跳回的位置 $p$。

如上文的例子，就是 $km{p}_6=3$。

容易发现 $s_2[1\dots p-1]$ 必须和 $s_2[j-p+1\dots j-1]$ 相等，不然跳了之后，无法匹配的上，如上例，$s_2[1\dots 2]$ 和 $s_2[4\dots 5]$ 是相等的。

所以求 $km{p}_j$ 就变成了，求 $s_2[1\dots j-1]$（这玩意就是 $s_2$ 的一个前缀）这个字符串的前缀和后缀相等的最大长度。

求 $kmp$ 就变成了，求 $s_2$ 所有前缀的前缀和后缀的最大长度。

发现这也恰好是题目要求的 border。

3. 实现

$km{p}_1=0$，模式串第一位都失配了不存在方案能够往前跳来匹配文本串的第 $i$ 位。

考虑让 $s_2$ 自己匹配自己：

for (int i = 2, j = 0; i <= ns2; i++) {
    while (j and s2[i] != s2[j + 1])
        j = kmp[j];
    if (s2[i] == s2[j + 1])
        j++;
    kmp[i] = j;
}

以 $\mathtt{\text{abadabaa}}$ 处理到第 $8$ 位为例，新进来了一个 a，因为 $s_2[1\dots 3]=s_2[5\dots 7]$，前一位 $km{p}_7$ 显然是 $3$，所以 $j=3$。

但是 $s_2[8]\ne s_2[j+1]$，即 $s_2[1\dots 4]$ 无法匹配上 $s_2[5\dots 8]$，因为 $s_2[1]=s_2[3]$，所以 $j$ 就往回跳回 $km{p}_3=1$。

但是 $s_2[2]\ne s_2[8]$，所以 $s_2[1\dots 2]$ 也无法匹配上 $s_2[7\dots 8]$，$j$ 接着往前跳到 $km{p}_1=0$。

$s_2[1]=s_2[8]$，匹配上了，所以 $km{p}_8=1$。

然后和文本串匹配：

for (int i = 1, j = 0; i <= ns1; i++) {
    while (j and s1[i] != s2[j + 1])
        j = kmp[j];
    if (s1[i] == s2[j + 1])
        j++;
    if (j == ns2) {
        cout << i - ns2 + 1 << "\n";
        // j == s2.size()说明s2匹配上s1的子串了 
        // 但是 i 是匹配上的位置的结尾，题目要求开头 
        j = kmp[j];
        // 匹配完了下一位绝对失配，先往前跳 
    }
}

4. 失配树

P5829 【模板】失配树。

把 $km{p}_i$ 作为 $i$ 的祖先所构成的树（显然树根为 $0$）。

性质：$s[1\dots i]$ 和 $s[1\dots j]$ 的最长公共 Border 的长度是 $i$ 和 $j$ 的最近公共祖先的编号 $lca$。

稍微推导一下即可：

• $s[1\dots km{p}_i]=s[i-km{p}_i+1\dots i]$，$s[1\dots km{p}_j]=s[j-km{p}_j+1\dots j]$

• $lca\le i,j$，总不可能一段区间的 Border 长度比这段区间还长。

• $s[1\dots lca]=s[i-lca+1\dots i]=s[j-lca+1\dots j]$。

代码与 KMP 高度重复，本文重点不是 LCA，故不放。

5. 刷题总结

(1). CF1200E Compress Words

找现在拼好的串的后缀，和新加入的串的前缀，的最长公共长度。考虑到 $km{p}_n$ 是整个串的前缀和后缀的最长公共部分。所以可以将拼好的串的后缀放在新加入的串的前缀的末尾，对于每个这种都跑一次 KMP 即可。由于不能重叠，两个部分之间最好加入一些分隔符。由于加入的后缀长度一定不超过新串，否则都是无意义的，所以时间复杂度是可以保证的，大概是 $2$ 倍常数。

(2). P4824 [USACO15FEB] Censoring S

用 CSPS 2023 T2 $50$ 分暴力的套路，可以用栈来实现消除操作，那么只需要像 KMP 模板一位一位匹配即可，不过需要用一个数组，来记录文本串和模式串匹配，弹出栈回到文本串位置 $x$ 的时候，模式串对应的位置。

(3). CF126B Password

首先肯定不能直接取 $km{p}_n$，遇到 $\mathtt{\text{aaaa}}$ 直接暴毙，考虑添加限制条件就会发现，$km{p}_n^{\prime }$ 必须要小于 $\underset{i=1}{\overset{n-1}{max}}km{p}_i$ 才有可能有合法答案，所以先跳一波 KMP 然后直接一个一个枚举，找到 $km{p}_n^{\prime }=km{p}_i$ 即可。

(4). P2375 [NOI2014] 动物园

手玩样例或者瞪眼法都能看出来，当不管是否重复的时候，$num$ 数组可以递推，即 $nu{m}_i\leftarrow nu{m}_{km{p}_i}+1$。

接着考虑重复，直接跳 KMP 跳到 $i$ 的一半以内的位置，取那个位置的 $num$ 即可。正确性随便口胡一下：根据 $i$ 动两步 $j$ 才能动一步，所以 $j$ 不需要反复重置。

(5). P3435 [POI2006] OKR-Periods of Words

只要使得 $[1,i]$ 的公共前缀和公共后缀最短，那么这个最短后缀的前面复制一遍显然可以达到最长值。

(6). UVA10298 Power Strings

跟上一题有异曲同工之妙。对若干个周期进行观察，会发现 $s[1\dots km{p}_n]$ 和 $s[n-km{p}_n+1\dots n]$ 必须有重叠部分或者相邻，进一步地，当 $nmod(n-km{p}_n)\equiv 0$ 时，才能形成周期，重复数为 $n÷(n-km{p}_n)$。正向证明较为复杂，分三类讨论即可。

(7). UVA11022 String Factoring

神秘题目没有数据范围，就朴素的利用 KMP 循环节优化区间 DP $O(n^3)$ 可过。简要介绍一下 $\mathtt{\text{DOODOO}}$ 的合并策略，首先发现两个 $\mathtt{\text{OO}}$ 均可以合并，所以 $f_{2,3}=f_{5,6}=1$。$f_{1,3}\leftarrow f_{1,1}+f_{2,3}=1$，这一部分是区间 DP 就能取到的转移。而 $[1,6]$ 可以合并，则 $f_{1,6}$ 选择其中一个循环节转移即可，$\leftarrow f_{1,3}$。会发现这是非常好写的。

(8). CF526D Om Nom and Necklace

把 $AB$ 捆包看作 $C$，会发现只有两种情况：第一种是 $CCC\dots C$ 形成若干个周期，另一种情况是 $CCC\dots CA$。考虑前面的 $C$ 被划分成 $k$ 个周期，显然只能 $\lfloor \frac{x}{k}\rfloor$（$x$ 是 $C$ 的个数），那么剩下的能够组成一个合法的 $A$ 而不会比 $C$ 还长，条件就是 $\lfloor \frac{x}{k}\rfloor >xmodk$，但是如果可以组成第一种情况，取等令最后的 $A$ 变成 $C$ 也是合法的。

(9). CF1286E Fedya the Potter Strikes Back

用 $ans$ 维护总答案，用 $ret$ 维护到操作 $i$ 时，以 $s[1\dots i]$ 的 border 的贡献。对于先前 $ret$ 维护中的 border，如果新插入的第 $i$ 位仍匹配，则仍存在，否则消失。所以需要用一种方式快速找到消失的 border。你会发现可能消失的 border 都是 $s[i-1]$ 失配树上的祖先。

设 $nx{t}_u$ 表示 $u$ 在失配树上的所有祖先中，离 $u$ 最近且满足 $s[p+1]\ne s[u+1]$ 的 $p$，也就是说，$nx{t}_u$ 是 $ret$ 仍维护的 border 中，消失的最长的前缀。则有：

• $s[i]\ne s[km{p}_{i-1}+1]$，那说明 $s[1\dots km{p}_{i-1}]$ 这个前缀消失了，$nx{t}_{i-1}=nx{t}_{km{p}_{i-1}}$。

• 否则，跳 $kmp$ 去寻找更短的前缀，但我们显然可以利用并查集思想，直接 $nx{t}_{i-1}=nx{t}_{km{p}_{i-1}}$。

接着，我们要减掉这些消失的 border 的权值，其实就是求一个右端点固定区间的最小值，ST 表或二分单调栈均可。还要把没有消失的 border 的权值大于 $w_i$ 的全部改成 $w_i$，用一个 map 维护每个 $w_i$ 出现的次数即可。

然后还有两种情况被漏算：一种是第一个字母和第 $i$ 个相同，特判。另一种是整个字符串，这种情况为了方便就不放进 map 和 $ret$ 里了，不然不好“消失”，而也是直接特判掉。

exKMP

P5410 【模板】扩展 KMP/exKMP（Z 函数）。

要求：

• $b$ 与 $b$ 的每一个后缀 的 LCP 长度数组 $Z$。

• $b$ 与 $a$ 的每一个后缀 的 LCP 长度数组 $P$。

1. 定义

LCP：最长公共前缀，即最长的相同的前缀。

2. 处理模式串本身的匹配

初始时，$Z_1=len(b)$。

如果已经处理完 $1\le i<x$ 的 $Z$ 情况，现在来求 $Z_x$：

先找 $i+Z_i-1$ 的最大值，把最大值出现的位置记为 $p$，最大值记为 $q$。

当然 $i$ 不能取 $1$，不然最大值一直都是 $len(b)$。

根据 $Z$ 函数的定义，可以知道 $b[1\dots Z_p]=b[p\dots q]$。

因此，$b[x-p+1\dots Z_p]=b[x\dots q]$。

令 $m=Z_{x-p+1}$。

现在有两种情况：

第一种 $x+m-1<q$，显然有 $b[1\dots m]=b[x-p+1\dots x-p+m]=b[x\dots x+m-1]$，那么 $Z_x=m$。

第二种 $x+m-1\ge q$（也是上例的情况），由于右边黄色的部分我们不知道会不会和 $b[m+1]$以及后面的字符串（左边的黄色部分）匹配，所以暴力枚举 $q$ 向右走直至不相等，可以证明出现枚举的情况时不会往回跑，所以总时间复杂度是 $O(n)$。

3. 处理模式串与文本串的匹配

思路和求 $Z$ 几乎一模一样，如果要求 $P_x$，找到 $i+P_i-1$ 的最大值的位置 $p$，$q=p+P_p-1$，$m$ 为 $Z_{x-k}$，用相同的推导方式求即可。

4. Code

void solveZ() {
    int p = 2, q = 1, m;
    Z[1] = lenb;
    while (q + 1 <= lenb and b[q] == b[q + 1])
        q++;
    Z[2] = q - 1;
    for (int i = 3; i <= lenb; i++) {
        q = p + Z[p] - 1;
        m = Z[i - p + 1];
        if (i + m - 1 < q)
            Z[i] = m;
        else {
            int j = max(0ll, q - i);
            while (i + j <= lenb and b[j + 1] == b[i + j])
                j++;
            Z[i] = j;
            p = i;
        }
    }
}
void solveP() {
    int p = 1, q = 0, m;
    while (q < lena and q < lenb and a[q + 1] == b[q + 1])
        q++;
    P[1] = q;
    for (int i = 2; i <= lena; i++) {
        q = p + P[p] - 1;
        m = Z[i - p + 1];
        if (i + m - 1 < q)
            P[i] = m;
        else {
            int j = max(0ll, q - i);
            while (i + j <= lena and j < lenb and b[j + 1] == a[i + j])
                j++;
            P[i] = j;
            p = i;
        }
    }
}

AC 自动机

给出 $n$ 个模式串和一个文本串，求在文本串中出现过的模式串的个数，或求出现次数最多的模式串，或求每个模式串出现的次数。

1. 前置知识

• Trie。

• KMP。

2. 建树和 fail 数组

先把模式串全部建到一个字典树上，在单词的结尾打上一个标记。

void update(string s) {
    int u = 0;
    for (int i = 0; i < s.size(); i++) {
        if (!trie[u][s[i] - 'a'])
            trie[u][s[i] - 'a'] = ++idx;
        u = trie[u][s[i] - 'a'];
    }
    cnt[u]++;
}

和 KMP 一样，AC 自动机需要一个 $fail$ 数组来处理如果下一位失配后应该指向。

举例说明：

• 若 $s_1=\mathtt{\text{abab}}$，$s_2=\mathtt{\text{bab}}$，$s_3=\mathtt{\text{ab}}$。

• 那么 $s_1$ 的 $\mathtt{\text{ab}}$ 指向 $s_3$ 的 $\mathtt{\text{ab}}$，$s_3$ 的 $\mathtt{\text{ab}}$ 指向 $s_2$ 的 $\mathtt{\text{b}}$。

• $s_1$ 的 $\mathtt{\text{aba}}$ 指向 $s_2$ 的 $\mathtt{\text{ba}}$

• $s_1$ 的 $\mathtt{\text{abab}}$ 指向 $s_2$ 的 $\mathtt{\text{bab}}$。

发现 $fail$ 指向当前字符串的后缀中，和其他字符串前缀相等的最长的，那个前缀的末尾（否则失配后无法继续和文本串匹配，其实和 KMP 是同理的）。

首先，每个模式串的第一位的 $fail$ 指向 Trie 的根，第一位就失配了只能从头开始。

然后用 BFS 求，流程如下：

• 如果 $u$ 存在子节点 $v$，子节点 $v$ 在字典树中代表的字符是 $c$，$v^{\prime }$ 表示 $fai{l}_u$ 的儿子中，代表字符 $c$ 的是 $v^{\prime }$；则 $fai{l}_v\leftarrow v^{\prime }$。

  • 如上文的 $s_1$ 和 $s_2$，$\mathtt{\text{aba}}$ 失配后指向 $\mathtt{\text{ba}}$，而两个都在后面加上一个相同的 $\mathtt{\text{b}}$，显然 $\mathtt{\text{abab}}$ 和 $\mathtt{\text{bab}}$ 仍能匹配。

• 如果 $u$ 不存在子节点 $v$，$v^{\prime }$ 的定义上面一样；则 $u$ 的代表 $c$ 的儿子直接从 $v$ 改成 $v^{\prime }$，继续匹配。

  • 如果到 $u$ 处，下一位字符 $c$ 会失配，那么肯定会实行不断跳 $fail$，直到一个节点有字符 $c$，这样地“不断跳”被卡的风险很高，还不如用并查集路径压缩的思想，直接指过去，找的时候也可以直接跳了。

void get_fail() {
    queue<int> q;
    for (int i = 0; i < 26; i++)
        if (trie[0][i]) {
            fail[trie[0][i]] = 0;
            q.push(trie[0][i]);
        }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; i++)
            if (trie[u][i]) {
                fail[trie[u][i]] = trie[fail[u]][i];
                q.push(trie[u][i]);
            } else
                trie[u][i] = trie[fail[u]][i];
    }
}

3. 询问

直接从字典树往下找，每找到一个串，说明它的所有失配指针指向的串都是可以匹配上的。

为了防止重复遍历，每统计完一个失配指针指向的串就给它打个标记。

(1). 统计有多少个模式串在文本串中出现过

P3808 AC 自动机（简单版）。

直接给遍历过的点的字典树的结尾标记全部加上即可。

int query(string s) {
    int u = 0, ret = 0;
    for (int i = 0; i < s.size(); i++) {
        u = trie[u][s[i] - 'a'];
        for (int tmp = u; tmp and cnt[tmp] != -1; tmp = fail[tmp]) {
            ret += cnt[tmp];
            cnt[tmp] = -1;
        }
    }
    return ret;
}

(2). 统计出现的次数

P3796 AC 自动机（简单版 II）。

把字典树的统计以当前节点结尾的字符串个数：cnt[u]++;，改成这个点代表哪个字符串结尾：

cnt[u] = id;

统计答案的时候就可以拿个数组算这个字符串出现了多少次，由于要统计次数，所以不需要且不能“防止重复遍历”：

for (int i = 0; i < s.size(); i++) {
    u = trie[u][s[i] - 'a'];
    for (int tmp = u; tmp; tmp = fail[tmp])
        ans[cnt[tmp]].cnt++;
}

4. 优化

P5357 【模板】AC 自动机。

由于失去了防止重复遍历的 break，上面 3. (2). 中的跳 $fail$ 可以被卡。

如 $fai{l}_1=2$，$fai{l}_2=3$，$\dots$，$fai{l}_{n-1}=n$。如果找到 $1$ 跳一次 $fail$，找到 $2$ 跳一次 $fail$，找到 $3$ 又跳一次 $fail$，直接被卡到 $O(n^2)$。

发现由所有 $fai{l}_u=v$ 中的 $(u,v)$ 边能构成一棵树，因此可以像线段树一样，找到几就给几加一个 $tag$，等到要跳 $fail$ 的时候直接拓扑排序然后一次全部转移。

此外，本题还有重复出现的模式串，可以用一个 $Map$ 数组将多个重复的模式串指向这个模式串第一个出现的位置，然后求答案和输出答案都直接输出 $an{s}_{Ma{p}_i}$ 即可。

处理重复（位于 update 函数）：

if (!cnt[u])
    cnt[u] = id;
Map[id] = cnt[u];

更新时统计以 $fail$ 边构成的入度（位于 get_fail 函数）：

if (trie[u][i]) {
    fail[trie[u][i]] = trie[fail[u]][i];
    idg[fail[trie[u][i]]]++;
    q.push(trie[u][i]);
}

统计答案时，改为标 $tag$：

void query(string s) {
    int u = 0;
    for (int i = 0; i < s.size(); i++) {
        u = trie[u][s[i] - 'a'];
        tag[u]++;
    }
}

拓扑排序并合并答案：

void topsort() {
    queue<int> q; 
    for (int i = 1; i <= idx; i++)
        if (!idg[i])
            q.push(i);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ans[cnt[u]] = tag[u];
        idg[fail[u]]--;
        tag[fail[u]] += tag[u];
        if (!idg[fail[u]])
            q.push(fail[u]);
    }
}

5. 刷题总结

(1)/(2). P3121 [USACO15FEB] Censoring G / P4824 [USACO15FEB] Censoring S

后面的弱化版可以用 KMP 做，上面有解法。

还是一样用栈消除操作，只不过这回变成了用 ACAM 匹配，开两个栈一个存 ACAM 节点匹配另一个存答案即可。

(3). P3966 [TJOI2013] 单词

如果 $u$ 节点和 $fai{l}_u$ 节点都有一个单词，那么 $fai{l}_u$ 自身出现了一次，在 $u$ 出现一次，贡献两个答案，因此只需要用 $cn{t}_{fai{l}_u}$ 加上 $cn{t}_u$ 即可，使用拓扑排序。

(4).P2444 [POI2000] 病毒

感觉这题也比较板，为啥是紫题？

如果 $fai{l}_u$ 节点有一个单词，而 $u$ 节点代表的单词包含 $fai{l}_u$ 代表的单词，所以 $u$ 也不能走，$cn{t}_u$ 要加上 $cn{t}_{fai{l}_u}$。

把字典树和 $fail$ 树一起看作一张图，其中 $x$ 指向 $fai{l}_x$。那么能无限循环，就说明能从根出发，在不经过不能走的点的前提下走出环。

无限不循环的情况理应不是题目考虑的范围。

然后这里有个小坑，正如小学学的无限循环小数一样，它可以是 $a.\dot{b}$，也可以是 $a.bc\dot{d}$，所以应该找一条从根出发的链下面接一个环。

(5)/(6). P3041 [USACO12JAN] Video Game G / SP10502 VIDEO - Video game combos

AC 自动机 dp 的常见套路，令 $f_{i,j}$ 表示当前考虑到答案字符串的第 $i$ 个字符为 AC 自动机上编号为 $j$ 的节点时的最大答案，则显然有：

$$f_{i,tri{e}_{j,p}}=max\{f_{i-1},j+cn{t}_{tri{e}_{j,p}}\}$$

其中 $cn{t}_x$ 表示以 $x$ 节点结尾的单词总数。所以同 (4)，在求 $fail$ 时，$cn{t}_x$ 要加上 $cn{t}_{fai{l}_x}$。

最终的答案即为 $max\{f_{k,i}\}$。

(7). P4052 [JSOI2007] 文本生成器

直接算合法的肯定不好搞，总数直接 ${26}^m$ 可得，减去完全不合法的方案即可。设 $f_{i,j}$ 表示到答案字符串的低 $i$ 个字符为 AC 自动机上编号为 $j$ 的节点且不经过任何单词的结尾的方案，变成了和 (5) 一样的问题。总不合法方案为 $\sum f_{m,i}$。

(8). P3311 [SDOI2014] 数数

这回从 (7) 变成算合法的方案数了，结合数位 dp 和上面同样的 dp 套路即可计算。需要注意处理前导零的情况，另外开一维 $0/1$ 表示当前这位还是或不是前导零。

(9). CF163E e-Government

首先前面提到的 $cn{t}_u\leftarrow cn{t}_u+cn{t}_{fai{l}_u}$ 肯定生效，所以增加或者删除一个字符串，本质就是给 $fail$ 树 上那个字符串的节点的子树里每个节点的点权都减去 $1$。学过树剖的都知道子树在 dfs 序上是连续的，所以可以直接用线段树维护查询，也可以差分一下用树状数组码量更小。

(10). P2414 [NOI2011] 阿狸的打字机

在 $a$ 单词里查询 $b$ 单词的出现次数，如果 $b$ 有出现，则一定会有一条来自 $a$ 某个字符的 $fail$ 一路指到 $b$ 的结尾，即查询 $b$ 结尾子树内的情况，跟 (9) 一样用 dfs 序，每次对 $a$ 的每个字符的节点都单点增加，树状数组查询 $b$ 结尾子树内的个数即可。

接着优化，根据本题字符串的构造方式，把询问离线下来，在同一个单词里查询的询问一次处理，按照逐步构造单词的顺序选择被查询的单词，可以做到 $O(n\log n)$ 完成所有询问。

(11). CF1207G Indie Album

跟 (10) 同理。

Manacher

P3805 【模板】manacher。

求字符串 $s$ 对于每个 $1\le i\le len(s)$，以 $s[i]$ 为对称中心的连续回文子串的长度。

首先，回文串有奇回文串和偶回文串两种，不好处理，如果在每两个字符之间以及开头前和结尾后加入一个间隔符 $\mathtt{\text{@}}$：

• 对于奇回文串，加入了偶数个 $\mathtt{\text{@}}$，所以还是奇回文串。

• 对于偶回文串，加入了奇数个 $\mathtt{\text{@}}$，也变成了奇回文串。

再在字符串的两端加入一个不同的起止符 ~ 和 $\mathtt{\text{!}}$。

接下来的思路和 exKMP 很像，设 $P_i$ 表示以 $i$ 为回文对称中心的最长回文半径（对于奇回文串，回文半径的长度还包括回文对称中心 $i$）。

假设当前求完了 $1\sim i-1$ 的 $P$，现在来求 $P_i$。

如果的向右遍历到的最大位置是 $r$，$r$ 这个位置是以 $mid$ 为回文中心的回文串的右边界，$l$ 是 $r$ 关于 $mid$ 的对称点，$j$ 是 $i$ 关于 $mid$ 的对称点。

• $j=mid-(i-mid)=mid\times 2-i$。

1. $mid<i<r$

(1). $i+P_j-1<r$

如上图，根据回文串的定义：

• 浅蓝色的部分等于深蓝色部分的反串（关于 $mid$ 对称）；

• 左边的深绿色部分等于左边的浅绿色部分的反串（关于 $j$ 对称）；

• 右边的深绿色部分等于左边的浅绿色部分的反串（关于 $mid$ 对称）；

• 右边的浅绿色部分等于左边的深绿色部分的反串（关于 $mid$ 对称）。

所以右边的浅绿色部分等于右边的深绿色部分的反串。

所以 $P_i=P_j$。

(2). $i+P_j-1\ge r$

和 exKMP 同理，当前不知道黄色的部分能不能匹配的上，所以 $P_i=r-i+1$ 然后暴力扩展并更新 $r$ 和 $mid$。

2. $i>r$

直接暴力扩展 $r$。

最后统计答案，当算上间隔符时，回文串的长度是 $P_i\times 2-1$，间隔符的个数是 $(P_i\times 2-1+1)÷2$（备注：$+1$ 用于向上取整），所以：

$$ans=P_i\times 2-1-(P_i\times 2-1+1)÷2=P_i-1$$

// 插入间隔符 
cin >> (tmp + 1);
n = strlen(tmp + 1);
s[1] = '~', s[2] = '#', m = 2;
for (int i = 1; i <= n; i++)
    s[m + 1] = tmp[i], s[m + 2] = '#', m += 2;
s[++m] = '!';
// 求最长回文半径 
for (int i = 2; i < m; i++) {
    if (i <= r)
        p[i] = min(p[mid * 2 - i], r - i + 1);
    else
        p[i] = 1;
    while (s[i - p[i]] == s[i + p[i]])
        p[i]++;
    if (i + p[i] - 1 >= r)
        r = i + p[i] - 1, mid = i;
    ans = max(ans, p[i] - 1);
}
cout << ans;

回文自动机

又叫回文树。

P5496 【模板】回文自动机（PAM）。

给定字符串 $s$，求对于每个 $i$，以 $i$ 位置为结尾的回文串个数。

1. 节点定义

每个节点代表一个字符，从一个节点走向根，再从根走回这个节点，经过的节点所代表的字符能构成一个回文串。

因此，每个节点也能代表一个本质不同的回文串。

在一个节点 $u$ 下面再挂一个节点 $v$，相当于在 $u$ 代表的回文串的两头都加上 $v$ 代表的字符，从而构成一个新的回文串，$le{n}_v\leftarrow le{n}_u+2$ 能得到 $v$ 代表的回文串的长度。

但是回文串有奇有偶，因此有两个根代表空串：偶根 $0$，$le{n}_0=0$；奇根 $1$，$le{n}_1=-1$。

• 因为奇根下挂的第一层子节点并不需要在空串的两头都加入，只有加入一个才能构成奇串。

除了两个根以外的节点总数就是这个字符串的回文子串总数。

2. 将新回文串放到回文树上的策略

其实模板的问题，换一种说法就是：

对于每个 $i$，求 $s[1\dots i]$ 的回文后缀的个数。

考虑如果已经处理完 $s[1\dots i-1]$ 的回文后缀，现在要处理以 $i$ 为结尾的回文串。

所有新加入的回文串 $s^{\prime }$，一定是最长的新的回文串 $s_{max}^{\prime }$的后缀（因为它们都以 $i$ 为结尾）。

除了 $s_{max}^{\prime }$ 以外，其他的 $s^{\prime }$ 显然可以通过 $s_{max}^{\prime }$ 的对称中心翻转到前面已经处理过的部分，可以直接挂在回文树上：

• 假设现在处理到 $i=9$。

• 蓝色部分是 $s_{max}^{\prime }$，$s_{max}^{\prime }$ 的对称中心是 $6$，浅绿色是一个 $s^{\prime }$。

• 深绿色是浅绿色的反串（关于 $6$ 对称）。

• 浅绿色是浅绿色的反串（它是新加入的回文串）。

• 深绿色是浅绿色。

• 由于回文树上的都是本质不同的字符串，深绿色和浅绿色本质相同，故浅绿色不需要添加到回文树上。

因此，每次只需要把 $s_{max}^{\prime }$ 挂到回文树上就行了，回文树上节点的个数是 $O(len(s))$ 级别的（同时，这里证明了一个字符串本质不同的回文子串最多只有 $len(s)$ 个）。

3. 考虑如何将 $s_{max}^{\prime }$ 挂到回文树上

类似于 AC 自动机，用类似于字典树的结构来存储回文树，定义 $fai{l}_x$ 表示 $x$ 代表的回文子串的除本身外的最长回文后缀的位置。

如上文的 $s[3\dots 9]=\mathtt{\text{baabaab}}$，他的最长回文后缀（除本身）是 $\mathtt{\text{baab}}$。故 $fail$（红色指针）如下图所示：

$fai{l}_0=1$，一个字符是回文串，因此奇根下面一定能挂点。

$fai{l}_1=0$，防止爆炸。

先从代表 $i-1$ 的节点跳 $fail$ 跳到 $x$，直到 $s[i-le{n}_x-1]=s[i]$（根据 $fail$ 的定义，$s[i-le{n}_x\dots i-1]$ 是回文串，因此 $s[i-le{n}_x-1\dots i]$ 也是回文串）。

根据节点的定义，可以直接将代表 $i$ 的节点 $y$ 挂到 $x$ 下面。

和 AC 自动机一样，$fai{l}_y$ 等于 $fai{l}_x$ 下代表 $s_i$ 字符的节点。

4. 求答案

设 $nu{m}_x$ 表示回文树上 $x$ 号点代表的回文串中回文后缀的个数。我们知道，除了新加入的最长回文后缀，其它回文后缀均已出现过并且被次长回文后缀包含，而次长回文后缀也是已知的，那么可以由它转移得到：

$$nu{m}_x=nu{m}_{fai{l}_x}+1$$

如果 $y$ 代表的回文串是 $s_{max}^{\prime }$，那么 $s[1\dots i]$ 的回文后缀个数就是 $nu{m}_y$。

namespace PAM {
    int len[N], num[N], fail[N], trie[N][27], idx = 1, now;
    char s[N];
    int getfail(int x, int i) {
        while (i - len[x] - 1 < 1 or s[i - len[x] - 1] != s[i])
            x = fail[x];
        return x;
    }
    void insert(int i) {
        int cur = getfail(now, i);
        if (!trie[cur][s[i] - 'a']) {
            fail[++idx] = trie[getfail(fail[cur], i)][s[i] - 'a'];
            trie[cur][s[i] - 'a'] = idx;
            len[idx] = len[cur] + 2;
            num[idx] = num[fail[idx]] + 1;
        }
        now = trie[cur][s[i] - 'a'];
    }
}
using namespace PAM;
signed main() {
    IOS;
    cin >> (s + 1);
    n = strlen(s + 1);
    fail[0] = 1, len[1] = -1;
    for (int i = 1; i <= n; i++) {
        insert(i);
        cout << num[now] << " ";
        s[i + 1] = (s[i + 1] + num[now] - 97) % 26 + 97;
    }
    return 0;
}