企业官网建设流程全解析

引言

信奥（信息学奥赛）新赛季冲刺阶段，字符串处理一直是提高组、省选的高频考点。从各地市级上机活动（例如近期正在报名的「包河区青少年信息学科普日活动」，区级上机测试即以 C++ 考查算法设计与编程调试）到各大杯赛，凡是涉及「文本查重、最长重复片段、词频统计、子串去重」的题目，几乎都能用后缀数组（Suffix Array，简称 SA）配上height 数组（相邻后缀的最长公共前缀 LCP）在线性对数时间内优雅解决。

很多同学熟悉后缀自动机（SAM），但 SAM 是在线自动机思路；后缀数组则是「把所有后缀按字典序排个序，再看相邻两个后缀的公共前缀」——两者解决同类问题，却是两套完全不同的工具。本文用一道原创题「校园征文库查重系统」带你吃透后缀数组，并给出 C++ 与 Python 双语言实现、复杂度分析与高频易错点。

题目 / 项目目标

【原创题】校园征文库查重系统

校广播台把往届优秀征文拼成一个长文本串S（长度n ≤ 10^5），运营同学想做三件事：

• 任务 A（查重）：找出可重叠的最长重复子串长度（即文中出现至少两次、可以重叠的最长片段）。
• 任务 B（去重统计）：统计S中本质不同的子串一共有多少个。
• 任务 C（高频片段）：给定整数k，找出至少出现k次的最长相同子串长度。

下面所有结论都建立在「后缀数组 + height 数组」之上，我们一步步拆解。

核心考点

1. 后缀数组sa[i]：把所有后缀S[i..n-1]按字典序从小到大排序后，第i名的后缀起始下标。
2. 名次数组rk[i]：后缀i在排序后的名次（0 起）。
3. height 数组height[i]：排第i的后缀与排第i-1的后缀的最长公共前缀长度 LCP，即LCP(sa[i-1], sa[i])。height[0] = 0。
4. 倍增 + 计数排序构造 SA：每次把「当前长度为k的块的排名」当作第一关键字、「向后k位的块的排名」当作第二关键字，稳定排序把长度翻倍，直到所有后缀互异。O(n log n)，空间O(n)。
5. height 的 O(n) 递推：利用height[rk[i]] ≥ height[rk[i-1]] - 1的性质，从前往后扫，总比较次数被摊还到O(n)。
6. 本质不同子串数=Σ (n - sa[i] - height[i])：每个后缀贡献「它自身长度」减去「与上一个后缀已重复的 prefix 长度」。
7. 至少出现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[i+k]，越界补 -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 k=2 最长 =", longest_k_repeat(h, 2)) # 3 print("C k=3 最长 =", longest_k_repeat(h, 3)) # 1 ("a")

C++ 实现

#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; pair<vector<int>, vector<int>> build_sa(const string& s) { int n = (int)s.size(); vector<int> 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) { vector<int> 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; vector<int> cnt(mxs, 0); for (int v : sec) cnt[v + 1]++; for (int i = 0; i < mxs - 1; i++) cnt[i + 1] += cnt[i]; vector<int> 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; vector<int> new_rk(n); new_rk[sa[0]] = 0; for (int i = 1; i < n; i++) { int prev = sa[i - 1], cur = sa[i]; pair<int, int> pv = {rk[prev], (prev + k < n) ? rk[prev + k] : -1}; pair<int, 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}; } vector<int> build_height(const string& s, const vector<int>& sa, const vector<int>& rk) { int n = (int)s.size(); vector<int> 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 vector<int>& sa, const vector<int>& 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 vector<int>& height) { int r = 0; for (int v : height) r = max(r, v); return r; } int longest_k_repeat(const vector<int>& height, int k) { int n = (int)height.size(); if (k <= 1) return n; if (k - 1 > n) return 0; vector<int> 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 k=2 最长 = " << longest_k_repeat(h, 2) << "\n"; // 3 cout << "C k=3 最长 = " << 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）。

七个易错点

1. 计数排序必须稳定：按(rk, sec)排序时两次排序都要从右向左放置，否则第二关键字相等的后缀顺序会被反转，排名错乱。这是后缀数组最经典的坑。
2. 第二关键字越界必须补极小值（-1）而非0：真实 rank 从 0 起，越界的「不存在的块」应排在所有人之前，补-1才能保证字典序正确。
3. 提前退出条件：当rk[sa[n-1]] == n-1（所有排名已连续互异）即可break，否则会多跑一轮甚至把 rank 算飞。
4. height 用 O(n) 递推而非逐对求 LCP：务必利用height[rk[i]] ≥ height[rk[i-1]] - 1的「起跳」性质，否则退化为O(n²)。
5. 本质不同子串公式：每个后缀贡献n - sa[i] - height[i]，注意height[0]恒为 0（排第一的后缀没有前一个）。
6. 任务 C 的窗口长度是k-1不是k：k个后缀之间有k-1条相邻 LCP；且k=1要特判为整串长度n，否则窗口退化出错。
7. 字符编码一致性：Python 用ord(c)取码、C++ 用unsigned char，都只依赖相对大小，ASCII 与 Unicode 均可用；但混用两种语言对拍时要保证同一字符串的码值语义一致。

进阶

• 两串最长公共子串：把S = A + '#' + B（#为两串均未出现的分隔符）拼起来建 SA，答案就是「相邻两个后缀分别来自 A、B 两侧」时的 height 最大值。
• 后缀数组 vs 后缀自动机（SAM）：SA 胜在好写、好调试、配合 height 能直接做「任意两后缀 LCP」类问题；SAM 胜在能在线增量、天然支持 endpos 计数。两者解决同类问题，但本文的「排序所有后缀再看相邻 LCP」思路与 SAM 的自动机思路互不替代，建议都掌握。
• 线性构造 DC3 / SA-IS：当n很大且对常数敏感（如 10⁶ 级以上）时，可上O(n)的 DC3 或 SA-IS；竞赛中O(n log n)倍增通常已足够。
• 任意两后缀 LCP（RMQ）：对 height 建 ST 表，则LCP(sa[i], sa[j]) = min(height[i+1..j])，可O(1)查询，进而支持「最长公共前缀」「重复次数」等离线统计。
• 练习推荐：洛谷 P3809【模板】后缀排序（练 SA 构造）、P2408 不同子串个数（练 height 公式）、POJ 3693 最长重复子串（练 height + 还原）。

小结与互动

后缀数组的核心就一句话：把后缀排好序，相邻看一眼 LCP（height），一半字符串问题迎刃而解。本文的「校园征文库查重系统」同时覆盖了可重叠最长重复子串、本质不同子串计数、k 次重复最长子串三个高频模型，建议把上面的 C++ / Python 代码亲手敲一遍、用banana等小样例验证，再去做洛谷模板题巩固。

你在备赛季里还被哪些字符串题卡住过？最长公共子串、后缀自动机、还是 Manacher 回文？欢迎在评论区留言，下一篇可以接着拆解。觉得有用别忘了点赞收藏，关注我，持续更新信奥算法干货。

📚 免费少儿编程资料（夸克网盘领取）

以下资料来自夸克网盘分享，点击链接可直接保存；若需在 App 内打开，也可复制下方明文链接：

1. 全国青少年信息素养大赛复赛集训题目Python&C++.docx
   https://pan.quark.cn/s/93995d3cb150
2. 2024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdf
   https://pan.quark.cn/s/da97b5dbf75d
3. Python背记手册.pdf
   https://pan.quark.cn/s/7568ae9ca92b
4. Python课程
   https://pan.quark.cn/s/a94bf02d00c6
5. 2024信息素养大赛图形化复赛集训题答案3-9
   https://pan.quark.cn/s/6ccab7ec3cbc
6. 2025年03月份电子学会考级真题
   https://pan.quark.cn/s/4403c4228912
7. 2025全国青少年信息素养大赛赛项说明
   https://pan.quark.cn/s/d9d0df4a9f29
8. 青少儿信息素养大赛编程资料
   https://pan.quark.cn/s/4ab6bd83be8a

资料持续更新，关注获取最新分享。