引言信奥信息学奥赛新赛季冲刺阶段字符串处理一直是提高组、省选的高频考点。从各地市级上机活动例如近期正在报名的「包河区青少年信息学科普日活动」区级上机测试即以 C 考查算法设计与编程调试到各大杯赛凡是涉及「文本查重、最长重复片段、词频统计、子串去重」的题目几乎都能用后缀数组Suffix Array简称 SA配上height 数组相邻后缀的最长公共前缀 LCP在线性对数时间内优雅解决。很多同学熟悉后缀自动机SAM但 SAM 是在线自动机思路后缀数组则是「把所有后缀按字典序排个序再看相邻两个后缀的公共前缀」——两者解决同类问题却是两套完全不同的工具。本文用一道原创题「校园征文库查重系统」带你吃透后缀数组并给出 C 与 Python 双语言实现、复杂度分析与高频易错点。题目 / 项目目标【原创题】校园征文库查重系统校广播台把往届优秀征文拼成一个长文本串S长度n ≤ 10^5运营同学想做三件事任务 A查重找出可重叠的最长重复子串长度即文中出现至少两次、可以重叠的最长片段。任务 B去重统计统计S中本质不同的子串一共有多少个。任务 C高频片段给定整数k找出至少出现k次的最长相同子串长度。下面所有结论都建立在「后缀数组 height 数组」之上我们一步步拆解。核心考点后缀数组sa[i]把所有后缀S[i..n-1]按字典序从小到大排序后第i名的后缀起始下标。名次数组rk[i]后缀i在排序后的名次0 起。height 数组height[i]排第i的后缀与排第i-1的后缀的最长公共前缀长度 LCP即LCP(sa[i-1], sa[i])。height[0] 0。倍增 计数排序构造 SA每次把「当前长度为k的块的排名」当作第一关键字、「向后k位的块的排名」当作第二关键字稳定排序把长度翻倍直到所有后缀互异。O(n log n)空间O(n)。height 的 O(n) 递推利用height[rk[i]] ≥ height[rk[i-1]] - 1的性质从前往后扫总比较次数被摊还到O(n)。本质不同子串数Σ (n - sa[i] - height[i])每个后缀贡献「它自身长度」减去「与上一个后缀已重复的 prefix 长度」。至少出现k次的最长子串在sa中连续k个后缀共享某前缀 ⟺ 它们之间k-1条相邻 height 都 ≥ 该长度等价于 height 上「长度k-1的窗口的最小值」的最大值单调队列O(n)。解法 / 拆解Python 实现def build_sa(s): 倍增 稳定计数排序构造后缀数组O(n log n)。 n len(s) rk [ord(c) for c in s] # 初始排名 字符编码 sa list(range(n)) k 1 while k n: # 第二关键字rk[ik]越界补 -1必须比任何真实 rank 都小 sec [rk[i k] if i k n else -1 for i in range(n)] # 按 sec 稳定计数排序从右向左放置保证等长关键字顺序不反转 mxs max(sec) 2 cnt [0] * mxs for v in sec: cnt[v 1] 1 for i in range(mxs - 1): cnt[i 1] cnt[i] tmp [0] * n for i in range(n - 1, -1, -1): v sec[sa[i]] 1 cnt[v] - 1 tmp[cnt[v]] sa[i] sa tmp # 按第一关键字 rk 稳定计数排序 mxr max(rk) 2 cnt [0] * mxr for v in rk: cnt[v 1] 1 for i in range(mxr - 1): cnt[i 1] cnt[i] tmp [0] * n for i in range(n - 1, -1, -1): v rk[sa[i]] 1 cnt[v] - 1 tmp[cnt[v]] sa[i] sa tmp # 重排 rank若已全员互异则提前结束 new_rk [0] * n new_rk[sa[0]] 0 for i in range(1, n): prev, cur sa[i - 1], sa[i] pv (rk[prev], rk[prev k] if prev k n else -1) cv (rk[cur], rk[cur k] if cur k n else -1) new_rk[cur] new_rk[prev] (1 if cv pv else 0) rk new_rk if rk[sa[-1]] n - 1: break k 1 return sa, rk def build_height(s, sa, rk): O(n) 求 height 数组。 n len(s) height [0] * n h 0 for i in range(n): if rk[i] 0: h 0 continue j sa[rk[i] - 1] while i h n and j h n and s[i h] s[j h]: h 1 height[rk[i]] h if h 0: h - 1 # 关键下一个 i 的 h 至少从 h-1 起跳 return height def distinct_substrings(s, sa, height): 本质不同子串个数 Σ(n - sa[i] - height[i])。 n len(s) return sum(n - sa[i] - height[i] for i in range(n)) def longest_repeat(height): 任务 A可重叠最长重复子串 height 最大值。 return max(height) if height else 0 def longest_k_repeat(height, k): 任务 C至少出现 k 次的最长子串。 n len(height) if k 1: return n # 整串本身至少出现 1 次 if k - 1 n: return 0 from collections import deque dq deque() best 0 for i in range(n): while dq and height[dq[-1]] height[i]: dq.pop() dq.append(i) if dq[0] i - (k - 1): # 窗口大小 k-1 条相邻 LCP dq.popleft() if i k - 2: best max(best, height[dq[0]]) return best # 示例 if __name__ __main__: S banana sa, rk build_sa(S) h build_height(S, sa, rk) print(sa , sa) # [5, 3, 1, 0, 4, 2] print(height , h) # [0, 1, 3, 0, 0, 2] print(本质不同子串数 , distinct_substrings(S, sa, h)) # 15 print(A 可重叠最长重复 , longest_repeat(h)) # 3 (ana) print(C k2 最长 , longest_k_repeat(h, 2)) # 3 print(C k3 最长 , longest_k_repeat(h, 3)) # 1 (a)C 实现#include iostream #include string #include vector #include algorithm using namespace std; pairvectorint, vectorint build_sa(const string s) { int n (int)s.size(); vectorint sa(n), rk(n); for (int i 0; i n; i) { sa[i] i; rk[i] (unsigned char)s[i]; } int k 1; while (k n) { vectorint sec(n); for (int i 0; i n; i) sec[i] (i k n) ? rk[i k] : -1; // 按 sec 稳定计数排序 int mxs *max_element(sec.begin(), sec.end()) 2; vectorint cnt(mxs, 0); for (int v : sec) cnt[v 1]; for (int i 0; i mxs - 1; i) cnt[i 1] cnt[i]; vectorint tmp(n); for (int i n - 1; i 0; i--) { int v sec[sa[i]] 1; cnt[v]--; tmp[cnt[v]] sa[i]; } sa tmp; // 按 rk 稳定计数排序 int mxr *max_element(rk.begin(), rk.end()) 2; cnt.assign(mxr, 0); for (int v : rk) cnt[v 1]; for (int i 0; i mxr - 1; i) cnt[i 1] cnt[i]; for (int i n - 1; i 0; i--) { int v rk[sa[i]] 1; cnt[v]--; tmp[cnt[v]] sa[i]; } sa tmp; vectorint new_rk(n); new_rk[sa[0]] 0; for (int i 1; i n; i) { int prev sa[i - 1], cur sa[i]; pairint, int pv {rk[prev], (prev k n) ? rk[prev k] : -1}; pairint, int cv {rk[cur], (cur k n) ? rk[cur k] : -1}; new_rk[cur] new_rk[prev] (cv pv ? 1 : 0); } rk new_rk; if (rk[sa[n - 1]] n - 1) break; // 已全部互异提前结束 k 1; } return {sa, rk}; } vectorint build_height(const string s, const vectorint sa, const vectorint rk) { int n (int)s.size(); vectorint height(n); int h 0; for (int i 0; i n; i) { if (rk[i] 0) { h 0; continue; } int j sa[rk[i] - 1]; while (i h n j h n s[i h] s[j h]) h; height[rk[i]] h; if (h 0) h--; } return height; } long long distinct_sub(const string s, const vectorint sa, const vectorint height) { int n (int)s.size(); long long r 0; for (int i 0; i n; i) r (n - sa[i] - height[i]); return r; } int longest_repeat(const vectorint height) { int r 0; for (int v : height) r max(r, v); return r; } int longest_k_repeat(const vectorint height, int k) { int n (int)height.size(); if (k 1) return n; if (k - 1 n) return 0; vectorint dq; int best 0; for (int i 0; i n; i) { while (!dq.empty() height[dq.back()] height[i]) dq.pop_back(); dq.push_back(i); if (dq.front() i - (k - 1)) dq.erase(dq.begin()); if (i k - 2) best max(best, height[dq.front()]); } return best; } int main() { ios::sync_with_stdio(false); cin.tie(0); string S banana; auto p build_sa(S); auto h build_height(S, p.first, p.second); cout 本质不同子串数 distinct_sub(S, p.first, h) \n; // 15 cout A 可重叠最长重复 longest_repeat(h) \n; // 3 cout C k2 最长 longest_k_repeat(h, 2) \n; // 3 cout C k3 最长 longest_k_repeat(h, 3) \n; // 1 return 0; }复杂度时间build_sa倍增O(log n)轮、每轮计数排序O(n)合计O(n log n)build_height摊还O(n)三问查询均O(n)任务 C 单调队列O(n)。整体O(n log n)。空间sa / rk / height / sec / cnt / tmp等数组均为O(n)合计O(n)约 6n 个 int。七个易错点计数排序必须稳定按(rk, sec)排序时两次排序都要从右向左放置否则第二关键字相等的后缀顺序会被反转排名错乱。这是后缀数组最经典的坑。第二关键字越界必须补极小值-1而非0真实 rank 从 0 起越界的「不存在的块」应排在所有人之前补-1才能保证字典序正确。提前退出条件当rk[sa[n-1]] n-1所有排名已连续互异即可break否则会多跑一轮甚至把 rank 算飞。height 用 O(n) 递推而非逐对求 LCP务必利用height[rk[i]] ≥ height[rk[i-1]] - 1的「起跳」性质否则退化为O(n²)。本质不同子串公式每个后缀贡献n - sa[i] - height[i]注意height[0]恒为 0排第一的后缀没有前一个。任务 C 的窗口长度是k-1不是kk个后缀之间有k-1条相邻 LCP且k1要特判为整串长度n否则窗口退化出错。字符编码一致性Python 用ord(c)取码、C 用unsigned char都只依赖相对大小ASCII 与 Unicode 均可用但混用两种语言对拍时要保证同一字符串的码值语义一致。进阶两串最长公共子串把S A # B#为两串均未出现的分隔符拼起来建 SA答案就是「相邻两个后缀分别来自 A、B 两侧」时的 height 最大值。后缀数组 vs 后缀自动机SAMSA 胜在好写、好调试、配合 height 能直接做「任意两后缀 LCP」类问题SAM 胜在能在线增量、天然支持 endpos 计数。两者解决同类问题但本文的「排序所有后缀再看相邻 LCP」思路与 SAM 的自动机思路互不替代建议都掌握。线性构造 DC3 / SA-IS当n很大且对常数敏感如 10⁶ 级以上时可上O(n)的 DC3 或 SA-IS竞赛中O(n log n)倍增通常已足够。任意两后缀 LCPRMQ对 height 建 ST 表则LCP(sa[i], sa[j]) min(height[i1..j])可O(1)查询进而支持「最长公共前缀」「重复次数」等离线统计。练习推荐洛谷 P3809【模板】后缀排序练 SA 构造、P2408 不同子串个数练 height 公式、POJ 3693 最长重复子串练 height 还原。小结与互动后缀数组的核心就一句话把后缀排好序相邻看一眼 LCPheight一半字符串问题迎刃而解。本文的「校园征文库查重系统」同时覆盖了可重叠最长重复子串、本质不同子串计数、k 次重复最长子串三个高频模型建议把上面的 C / Python 代码亲手敲一遍、用banana等小样例验证再去做洛谷模板题巩固。你在备赛季里还被哪些字符串题卡住过最长公共子串、后缀自动机、还是 Manacher 回文欢迎在评论区留言下一篇可以接着拆解。觉得有用别忘了点赞收藏关注我持续更新信奥算法干货。 免费少儿编程资料夸克网盘领取以下资料来自夸克网盘分享点击链接可直接保存若需在 App 内打开也可复制下方明文链接全国青少年信息素养大赛复赛集训题目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背记手册.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython课程https://pan.quark.cn/s/a94bf02d00c62024信息素养大赛图形化复赛集训题答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份电子学会考级真题https://pan.quark.cn/s/4403c42289122025全国青少年信息素养大赛赛项说明https://pan.quark.cn/s/d9d0df4a9f29青少儿信息素养大赛编程资料https://pan.quark.cn/s/4ab6bd83be8a资料持续更新关注获取最新分享。