- DL24JP 的博客
NOI算法2 字符串算法
-
DL24JP @ 2026-10-9 16:39:55
1.Manacher算法
-
洛谷题目：P3805 Manacher
题目描述
给出一个只由小写英文字符 $\texttt a,\texttt b,\texttt c,\ldots\texttt y,\texttt z$ 组成的字符串 ,求 中最长回文串的长度 。
字符串长度为 。
输入格式
一行小写英文字符 $\texttt a,\texttt b,\texttt c,\cdots,\texttt y,\texttt z$ 组成的字符串 。
输出格式
一个整数表示答案。
输入输出样例 #1
输入 #1
aaa
输出 #1
3
说明/提示
。
Manacher 算法（马拉车算法），用于在线性时间 O (n) 内求解一个字符串的最长回文子串长度。
1.1 核心思路是：
-
字符串预处理：在原字符串的每个字符两侧插入分隔符（如#），消除奇偶长度回文的差异，统一处理；
-
回文半径数组 d：d[i]表示以预处理后字符串的第i位为中心的最长回文子串的半径（包含中心本身）；
-
利用回文对称性优化：通过维护当前已知的最右回文边界[l, r]，减少重复匹配，将时间复杂度降至 O (n)；
-
结果转换：预处理后的回文半径减 1，即为原字符串的最长回文子串长度。
1.2 字符串预处理的作用：
-
原字符串abba → 预处理后#a#b#b#a#，最长回文半径为 5，5-1=4（原长度）；
-
原字符串abcba → 预处理后#a#b#c#b#a#，最长回文半径为 6，6-1=5（原长度）；
-
统一奇偶长度回文的处理逻辑，无需分情况讨论。
1.3 回文半径数组 d 的含义：
-
对于预处理后的字符串s，d[i]表示以s[i]为中心的最长回文子串的半径（包含中心）；
-
例如s[i] = #，d[i] = 3，则回文子串为s[i-2..i+2]，长度为2*3-1=5，对应原字符串长度为3-1=2。
1.4 最右回文边界 [l, r] 的优化逻辑：
-
当i在[l, r]内时，利用回文的对称性，直接复用对称位置的d值，避免重复匹配；
-
r-i+1是i到r的距离，确保d[i]不会超出当前最右边界，否则需要暴力扩展。
1.5 哨兵字符s[0] = '$'：
- 避免在while循环中访问s[-1]等越界位置，因为s[0]是特殊字符，永远不会和其他字符相等，循环会自动终止。
1.6 时间复杂度：
- 每个字符最多被扩展一次（暴力扩展的总次数为 O (n)），因此整体时间复杂度为 O (n)。
参考代码
// Manacher算法：线性时间求解最长回文子串长度 O(n)
#include<bits/stdc++.h>
using namespace std;
// 常量定义：N需足够大，覆盖预处理后的字符串长度（原字符串长度*2+2）
const int N = 3e7;
char a[N]; // 存储原始输入字符串（下标从1开始）
char s[N]; // 存储预处理后的字符串（插入分隔符#，消除奇偶回文差异）
int d[N]; // 回文半径数组：d[i]表示以s[i]为中心的最长回文子串的半径（包含中心）
/*
* 计算预处理后字符串s的回文半径数组d
* s 预处理后的字符串（下标从1开始）
* n 预处理后字符串的长度
*/
void get_d(char *s, int n)
{
// 初始化：预处理后字符串第一个有效位置（s[1]是#）的回文半径为1（仅自身）
d[1] = 1;
// i：当前遍历的中心位置；l/r：当前已知的最右回文子串的左/右边界（初始r=1）
for (int i = 2, l, r = 1; i <= n; i++)
{
// 第一步：核心优化：利用回文对称性，减少重复匹配
if (i <= r) // 当前中心i在最右回文边界r内，可复用对称位置的回文半径
{
// r-i+l：i关于当前回文中心（(l+r)/2）的对称位置
// min(d[对称位置], r-i+1)：取较小值，避免超出当前最右边界r
d[i] = min(d[r - i + l], r - i + 1);
}
// 第二步：暴力扩展：以i为中心，向左右匹配，直到字符不相等
// s[i-d[i]] 是当前左边界，s[i+d[i]] 是当前右边界
while (s[i - d[i]] == s[i + d[i]])
d[i]++; // 匹配成功，回文半径+1
// 第三步：更新最右回文边界：如果当前回文的右边界超出r，则更新l和r
if (i + d[i] - 1 > r)
{
l = i - d[i] + 1; // 新回文的左边界
r = i + d[i] - 1; // 新回文的右边界
}
}
}
int main()
{
// 读取原始字符串，存储到a[1]开始的位置（方便后续预处理）
scanf("%s", a + 1);
// n：原始字符串长度；k：预处理后字符串的下标指针（初始0）
int n = strlen(a + 1), k = 0;
// 预处理字符串：消除奇偶长度回文的差异
s[0] = '$'; // 哨兵字符（避免越界，s[0]永远不会和其他字符匹配）
s[++k] = '#'; // 第一个分隔符
// 遍历原始字符串，插入字符+分隔符
for (int i = 1; i <= n; i++)
{
s[++k] = a[i]; // 插入原始字符
s[++k] = '#'; // 插入分隔符
}
n = k; // 更新n为预处理后字符串的长度
// 计算回文半径数组d
get_d(s, n);
// 遍历d数组，找到最大的回文半径
int ans = 0;
for (int i = 1; i <= n; i++)
ans = max(ans, d[i]);
// 结果转换：预处理后的回文半径-1 = 原字符串的最长回文子串长度
// 例如：预处理后半径为4（#a#b#a#），对应原字符串abba，长度3（4-1）
printf("%d\n", ans - 1);
return 0;
}
2.后缀数组
-
洛谷题目：P3809 后缀排序
题目描述
读入一个长度为 的由大小写英文字母或数字组成的字符串，请把这个字符串的所有非空后缀按字典序（用 ASCII 数值比较）从小到大排序，然后按顺序输出后缀的第一个字符在原串中的位置。位置编号为 到 。
输入格式
一行一个长度为 的仅包含大小写英文字母或数字的字符串。
输出格式
一行，共 个整数，表示答案。
输入输出样例 #1
输入 #1
ababa
输出 #1
5 3 1 4 2
说明/提示
。
倍增法构造后缀数组（SA） 并求解height数组，核心功能是在 O (n log n) 时间复杂度内生成字符串的后缀数组，是处理字符串后缀相关问题（如最长重复子串、最长公共前缀等）的基础算法。
2.1 核心概念定义
-
后缀数组（sa）：sa[i] 表示排名为i的后缀的起始位置（字符串下标从 1 开始）；
-
排名数组（rk）：rk[i] 表示起始位置为i的后缀的排名；
-
height 数组：height[i] 表示排名为i的后缀与排名为i-1的后缀的最长公共前缀（LCP） 长度。
2.2 算法核心流程
-
get_sa 函数：采用「倍增法 + 基数排序」构造后缀数组。先按后缀的前 1 个字符排序，再依次按前 2、4、8...2^k 个字符排序（倍增），每次排序通过基数排序保证效率，直到所有后缀排名唯一；
-
get_height 函数：利用height数组的性质（height[rk[i]] ≥ height[rk[i-1]] - 1），线性时间求解height数组；
-
main 函数：输入字符串、初始化参数、调用上述函数，最终输出后缀数组。
2.3 基数排序的稳定性
-
基数排序采用逆序遍历将元素放入 sa 数组，保证相同关键字的元素相对顺序不变（稳定性），这是倍增法正确的关键。
-
双关键字排序时，先按第二关键字排序，再按第一关键字排序，符合基数排序 “低位优先” 的逻辑。
2.4 倍增法的核心优化
-
每次排序仅基于前 2^k 个字符，无需显式存储后缀的所有字符，通过 “排名合并” 实现高效排序；
-
当m == n时，所有后缀的排名唯一，提前退出循环，减少不必要的计算。
2.5 height 数组的核心性质
-
对于后缀i（起始位置），设rk[i] = r，则height[r] ≥ height[r-1] - 1；
-
该性质的意义：无需从 0 开始比较公共前缀，而是从height[rk[i-1]] - 1开始，将时间复杂度从 O (n²) 降至 O (n)。
2.6 数组下标从 1 开始的原因
-
避免后缀起始位置 + k 时出现 0 的情况（如sa[i]+k），简化越界判断（超出 n 的部分视为排名 0，无需额外处理）；
-
基数排序的计数数组c从 1 开始，与字符 ASCII 码（≥'a'=97）匹配，避免混淆。
2.7 变量 m 的作用
-
初始m=122（小写字母 z 的 ASCII 码），覆盖所有小写字母的初始排名；
-
倍增过程中m动态更新为当前排名的最大值，若m==n说明所有后缀排名唯一，提前终止。
参考代码
#include <bits/stdc++.h>
using namespace std;
// 数组大小：需覆盖字符串最大长度（题目中字符串长度≤2e6）
const int N = 2000010;
char s[N]; // 存储输入字符串，下标从1开始（避免越界，方便后缀操作）
int n, m; // n：字符串长度（等价于后缀个数）；m：基数排序的桶大小（初始为字符ASCII最大值）
// 核心数组说明：
int x[N]; // 第一关键字数组：x[i]表示起始位置为i的后缀的当前排名（按前2^k个字符）
int y[N]; // 辅助数组：①存储按第二关键字排序后的后缀起始位置 ②临时存储旧的x数组（排名）
int c[N]; // 计数数组：基数排序的桶，统计每个排名/字符的出现次数
int sa[N]; // 后缀数组：sa[i]表示排名为i的后缀的起始位置
int rk[N]; // 排名数组：rk[i]表示起始位置为i的后缀的排名
int height[N]; // height数组：height[i] = LCP(sa[i], sa[i-1])（排名i和i-1的后缀的最长公共前缀）
/*
* 倍增法构造后缀数组（SA）
* 核心思想：按后缀的前2^k个字符排序，每次基于前k个字符的排名，通过基数排序合并为前2k个字符的排名
* 时间复杂度：O(n log n)（基数排序O(n)，倍增次数O(log n)）
*/
void get_sa()
{
int i, j, k;
// 第一步：按后缀的前1个字符（即单个字符）进行基数排序（初始化）
// 1. 统计每个字符的出现次数（x[i] = s[i]，即字符的ASCII值作为初始排名）
for (i = 1; i <= n; i++) c[x[i] = s[i]]++;
// 2. 前缀和处理：c[i]表示≤i的字符的总个数，确定每个字符的排名范围
for (i = 1; i <= m; i++) c[i] += c[i - 1];
// 3. 逆序遍历：将后缀按字符放入sa数组（保证基数排序的稳定性）
for (i = n; i; i--) sa[c[x[i]]--] = i;
// 第二步：倍增过程（k为当前排序的字符长度的一半，2^k）
for (k = 1; k <= n; k <<= 1) // 每次k翻倍，直到2^k ≥ n
{
// 阶段1：按第二关键字排序（后缀的后k个字符的排名）
memset(c, 0, sizeof(c)); // 清空计数数组
// y数组暂存当前sa数组（按前k个字符排好的后缀），作为第二关键字排序的候选
for (i = 1; i <= n; i++) y[i] = sa[i];
// 统计第二关键字的出现次数：x[y[i]+k]是后缀y[i]的后k个字符的排名（第二关键字）
// 注：若y[i]+k >n，说明该后缀的后k个字符不存在，排名视为0（c[0]初始为0，无需处理）
for (i = 1; i <= n; i++) c[x[y[i] + k]]++;
// 前缀和确定第二关键字的排名范围
for (i = 1; i <= m; i++) c[i] += c[i - 1];
// 逆序遍历：按第二关键字将后缀放入sa数组（完成第二关键字排序）
for (i = n; i; i--) sa[c[x[y[i] + k]]--] = y[i];
// 阶段2：按第一关键字排序（后缀的前k个字符的排名）
memset(c, 0, sizeof(c)); // 清空计数数组
// y数组暂存按第二关键字排好的sa数组，作为第一关键字排序的候选
for (i = 1; i <= n; i++) y[i] = sa[i];
// 统计第一关键字的出现次数：x[y[i]]是后缀y[i]的前k个字符的排名（第一关键字）
for (i = 1; i <= n; i++) c[x[y[i]]]++;
// 前缀和确定第一关键字的排名范围
for (i = 1; i <= m; i++) c[i] += c[i - 1];
// 逆序遍历：按第一关键字将后缀放入sa数组（完成双关键字排序）
for (i = n; i; i--) sa[c[x[y[i]]]--] = y[i];
// 阶段3：重新计算排名x数组（合并前k和后k的排名，生成前2k个字符的新排名）
// y数组暂存旧的x数组（前k个字符的排名），用于比较是否相同
for (i = 1; i <= n; i++) y[i] = x[i];
m = 0; // 重置新排名的最大值（从0开始）
for (i = 1; i <= n; i++)
{
// 若两个后缀的前k个字符排名（y[sa[i]]）和后k个字符排名（y[sa[i]+k]）都相同
// 则它们的前2k个字符排名相同，否则新排名+1
if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
x[sa[i]] = m; // 排名不变
else
x[sa[i]] = ++m; // 排名递增
}
// 优化：若所有后缀排名唯一（m==n），无需继续倍增
if (m == n) break;
}
}
/**
* 求解height数组
* 核心性质：height[rk[i]] ≥ height[rk[i-1]] - 1，利用该性质避免重复比较，线性时间求解
* 时间复杂度：O(n)
*/
void get_height()
{
int i, j, k;
// 第一步：由sa数组推导rk数组（sa和rk互为逆运算）
// sa[i]是排名i的后缀位置 → rk[sa[i]] = i
for (i = 1; i <= n; i++) rk[sa[i]] = i;
// 第二步：遍历每个后缀i（起始位置），计算height[rk[i]]
k = 0; // k表示当前公共前缀的长度，初始为0
for (i = 1; i <= n; i++)
{
// 排名为1的后缀没有前驱，height[1] = 0，直接跳过
if (rk[i] == 1) continue;
// 核心优化：height[rk[i]] ≥ height[rk[i-1]] - 1，因此k先减1
if (k) k--;
// j是排名比i小1的后缀的起始位置（即sa[rk[i]-1]）
j = sa[rk[i] - 1];
// 暴力扩展公共前缀：直到字符不相等或超出字符串长度
while (i + k <= n && j + k <= n && s[i + k] == s[j + k])
k++;
// height[rk[i]] 是后缀i和其前驱后缀j的最长公共前缀长度
height[rk[i]] = k;
}
}
int main()
{
// 输入字符串，存储到s[1]开始的位置（方便后缀操作）
scanf("%s", s + 1);
// n：字符串长度（后缀个数）；m初始化为'z'的ASCII码（122），覆盖所有小写字母
n = strlen(s + 1);
m = 122;
// 构造后缀数组
get_sa();
// 求解height数组（本示例未输出height，仅演示构造）
get_height();
// 输出后缀数组：sa[1]~sa[n] 依次为排名1~n的后缀起始位置
for (int i = 1; i <= n; i++)
printf("%d ", sa[i]);
return 0;
}
3.后缀自动机
-
洛谷题目：P3804 后缀自动机 (SAM)
题目描述
给定一个只包含小写字母的字符串 。
请你求出 的所有出现次数不为 的子串的出现次数乘上该子串长度的最大值。
输入格式
一行一个仅包含小写字母的字符串 。
输出格式
一个整数，为所求答案。
输入输出样例 #1
输入 #1
abab
输出 #1
4
说明/提示
对于 的数据，。 对于 的数据，。
后缀自动机（SAM, Suffix Automaton），核心功能是求解字符串中「出现次数≥2 的子串的（长度 × 出现次数）的最大值」。SAM 是处理字符串子串问题的高效数据结构，时间 / 空间复杂度均为 O (n)（n 为字符串长度）。
3.1 核心概念与流程
-
SAM 的核心结构：
-
状态（State）：每个状态代表一组「endpos 集合相同」的子串（endpos 是子串在原字符串中结束位置的集合）；
-
转移边（ch）：ch[u][c]表示状态 u 接受字符 c 后转移到的状态；
-
后缀链接（fa）：fa[u]指向 u 的后缀状态（对应更短的子串）；
-
长度（len）：len[u]是状态 u 对应的最长子串的长度。
-
-
extend 函数：SAM 的核心构建函数，逐个添加字符，维护状态、转移边和后缀链接，处理「状态分裂」的特殊情况；
-
后缀链接树遍历（dfs）：SAM 的后缀链接构成一棵树，通过 DFS 累加每个状态的 endpos 大小（即子串出现次数 cnt），并计算目标最大值；
-
结果计算：遍历所有状态，找到cnt[u]>1时cnt[u] * len[u]的最大值（出现次数≥2 的子串，长度 × 次数最大）。
3.2 SAM 的状态与 endpos 集合
-
每个状态对应一组「endpos 集合相同」的子串：例如状态 u 的 endpos={3,5}，表示该状态的所有子串都在原字符串的 3、5 位置结束；
-
len[u]是状态 u 最长子串的长度，len[fa[u]]是其最短子串的长度 - 1（状态 u 的子串长度范围：(len[fa[u]], len[u]]）；
-
cnt[u]最终表示 endpos 集合的大小（子串出现次数），初始时只有「新建的状态（np）」cnt=1，其余为 0，需通过后缀链接树 DFS 累加。
3.3 extend 函数的三种核心情况
| 情况 | 条件 | 处理方式 |
|---|---|---|
| 新字符无匹配转移 | p 回跳到根（p=0） | fa[np] = 1（根节点） |
| 转移状态长度匹配 | len[q] = len[p]+1 | fa[np] = q |
| 转移状态长度过长 | len[q] > len[p]+1 | 分裂 q 为 nq，调整转移和后缀链接 |
状态分裂的意义：当len[q] > len[p]+1时，q 的最长子串长度超过了「p 添加字符 c」应有的长度，需分裂出 nq 来匹配该长度，保证 SAM 的「每个状态对应唯一 endpos 集合」的性质。
3.4 后缀链接树的作用
-
SAM 的后缀链接（fa）构成一棵树（根为 1），树中父节点的 endpos 集合是子节点的超集；
-
DFS 遍历该树时，子节点的 cnt 会累加到父节点，最终cnt[u]等于状态 u 的 endpos 集合大小（子串出现次数）；
-
例如：若状态 v 是 u 的子节点，则 v 的子串是 u 的子串的后缀，因此 v 的出现次数需计入 u。
3.5 答案计算逻辑
-
要求子串出现次数≥2（cnt[u]>1），此时cnt[u] * len[u]表示「长度为 len [u] 的子串出现了 cnt [u] 次」，取最大值即为题目所求；
-
若所有子串都只出现 1 次，ans 保持初始值 0（符合逻辑）。
参考代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6 + 10; // 状态总数上限（SAM的状态数不超过2n）
char str[N]; // 输入的原始字符串
vector<int> e[N]; // 后缀链接树的邻接表（用于DFS遍历）
LL cnt[N]; // cnt[u]：状态u对应的endpos集合大小（子串出现次数）
LL ans; // 最终答案：max(cnt[u] * len[u])（cnt[u]>1）
int tot = 1; // SAM的状态总数，初始根节点为1
int np = 1; // 「最后状态」指针，初始指向根节点
// SAM核心数组：
int fa[N]; // fa[u]：状态u的后缀链接（指向父状态）
int ch[N][26]; // ch[u][c]：状态u接受字符c（0-25对应a-z）后转移到的状态
int len[N]; // len[u]：状态u对应的最长子串的长度
/**
* SAM的核心扩展函数：添加字符c（0-25），构建SAM的状态和边
* c 待添加的字符（已转换为0-25的整数）
* 核心逻辑：
* 1. 新建状态np，初始化其长度和出现次数；
* 2. 从当前最后状态p回跳，为p添加指向np的转移边（若不存在）；
* 3. 处理三种情况：
* - p回跳到根（p=0）：np的后缀链接指向根；
* - 转移状态q的长度符合预期：np的后缀链接指向q；
* - 转移状态q的长度不符合：分裂q为nq，调整转移和后缀链接。
*/
void extend(int c)
{
// p：回跳指针，初始指向「添加字符前的最后状态」np（旧值）；np：新建的状态
int p = np;
np = ++tot; // 新建状态，状态总数+1
len[np] = len[p] + 1;// 新状态的最长子串长度 = 原最后状态长度 + 1（新增一个字符）
cnt[np] = 1; // 新状态初始出现次数为1（对应当前字符的结束位置）
// 阶段1：从p沿后缀链接回跳，为所有无c转移的状态添加指向np的转移边
for (; p && !ch[p][c]; p = fa[p])
ch[p][c] = np;
// 阶段2：处理后缀链接
if (p == 0) // 情况1：p回跳到根（无匹配的转移），np的后缀链接指向根（1）
fa[np] = 1;
else // 情况2：p找到有c转移的状态，q是该转移的目标状态
{
int q = ch[p][c];// q：p通过c转移到达的状态
if (len[q] == len[p] + 1) // 子情况2.1：q的长度恰好是p的长度+1（符合预期）
fa[np] = q; // np的后缀链接直接指向q
else // 子情况2.2：q的长度过长，需要分裂q为新状态nq
{
int nq = ++tot; // 新建分裂状态nq
len[nq] = len[p] + 1; // nq的最长子串长度 = p的长度+1（匹配当前转移的长度）
// 步骤1：调整后缀链接
fa[nq] = fa[q]; // nq的后缀链接继承q的后缀链接
fa[q] = nq; // q的后缀链接指向nq（q成为nq的子节点）
fa[np] = nq; // np的后缀链接指向nq（替代原来的q）
// 步骤2：修正转移边：所有从p回跳路径上指向q的c转移，改为指向nq
for (; p && ch[p][c] == q; p = fa[p])
ch[p][c] = nq;
// 步骤3：复制q的转移边到nq（nq和q共享除长度外的转移）
memcpy(ch[nq], ch[q], sizeof(ch[q]));
}
}
}
/**
* 遍历后缀链接树，累加每个状态的endpos大小（cnt），并计算答案
* u 当前遍历的状态（从根节点1开始）
* 核心逻辑：
* 1. 递归遍历u的所有子节点（后缀链接树的子节点）；
* 2. 累加子节点的cnt到u的cnt（endpos集合大小是子节点的并集）；
* 3. 若u的出现次数>1，更新答案为max(ans, cnt[u]*len[u])。
*/
void dfs(int u)
{
// 遍历u的所有子节点（后缀链接树中，fa[v]=u则v是u的子节点）
for (auto v : e[u])
{
dfs(v); // 递归处理子节点
cnt[u] += cnt[v]; // 累加子节点的出现次数到当前节点
}
// 若当前状态的子串出现次数≥2，计算长度×次数，更新最大值
if (cnt[u] > 1)
ans = max(ans, cnt[u] * len[u]);
}
int main()
{
// 输入字符串（存储到str数组）
scanf("%s", str);
// 逐个字符扩展SAM：将字符转换为0-25（a-z），调用extend
for (int i = 0; str[i]; i++)
extend(str[i] - 'a');
// 构建后缀链接树的邻接表：fa[i]是i的父节点，将i加入fa[i]的子节点列表
// 状态从2开始（根节点1无父节点）
for (int i = 2; i <= tot; i++)
e[fa[i]].push_back(i);
// 从根节点1开始DFS，统计cnt并计算答案
dfs(1);
// 输出最终答案
printf("%lld\n", ans);
return 0;
}