子串数目计算全解析：从基础逻辑到通用公式
在字符串处理、算法竞赛以及日常编程面试中，“求子串数目”是一个基础但极易混淆的问题。很多的初学者容易将子串（Substring）与子序列（Subsequence）的概念混淆，或者忽略了去重这一关键步骤。
这篇文章将深入探讨如何计算字符串中不同子串的数量，从最基础的数学公式推导，到处理重复字符的高级算法，凭借表格总结不同场景下的解决方案。
核心概念辨析
在引入公式之前，必须明确两个概念的区别，鉴于它们的计算逻辑截然不同：
子串 (Substring)：字符串中连续的一段字符序列。，`"abc"` 的子串包括 `"a"`, `"b"`, `"c"`, `"ab"`, `"bc"`, `"abc"`。
子序列 (Subsequence)：字符串中不连续的字符组成的序列（保持相对顺序）。，`"abc"` 的子序列涵盖 `"a"`, `"b"`, `"c"`, `"ab"`, `"ac"`, `"bc"`, `"abc"`。
这篇文章重点讨论：子串（Substring）的数目计算。
场景一：所有字符均不相同（基础公式）
假设字符串 的长度为 ，且字符串中所有字符互不相同。
1 逻辑推导
一个子串由起始位置 和结束位置 决定（）。 长度为 1 的子串有 个。 长度为 2 的子串有 个。 ... 长度为 的子串有 个。因此，总子串数（包含重复出现的相同内容，但由于字符不同，这里每个子串内容唯一）为等差数列求和：
2 示例
字符串 `S = "abc"` ()子串为：`a`, `b`, `c`, `ab`, `bc`, `abc`。
场景二：存在重复字符（去重问题）
当字符串中存在重复字符时（如 `"aba"`），直接使用 会计算包含重复内容的子串。 `"aba"` 中，索引 0 的 `"a"` 和索引 2 的 `"a"` 内容相同，但它们是不同的子串实例。
面试题或实际应用中所指的“子串数目”，指的是“不同子串（Distinct Substrings）”的数量。
1 暴力法（Brute Force）
1. 生成所有的子串。 2. 将子串存入 HashSet 中。 3. 返回 HashSet 的大小。时间复杂度： 或 ，取决于哈希操作和字符串比较。
适用性：仅适用于极短字符串（）。
2 后缀数组/后缀自动机（高级算法）
对于长字符串，我们需要更高效的算法。这里介绍基于后缀数组（Suffix Array）和最长公共前缀（LCP）的通用公式。核心原理
1. 生成字符串的所有后缀。 2. 将所有后缀按字典序排序。 3. 计算相邻两个后缀的最长公共前缀（LCP）长度。通用公式
设 为排序后第 个后缀的起始索引， 为 和 的最长公共前缀长度。不同子串的总数公式为：
或者更直观的理解：
解释：所有子串的总数减去重复计算的部分。 显示当前后缀与前一个后缀共享的前缀部分，这些前缀对应的子串已经在之前计算过了，因此需要减去。
3 示例演算
字符串 `S = "aba"` 1. 所有后缀：- `"aba"` (索引 0)
- `"ba"` (索引 1)
- `"a"` (索引 2)
- `SA[0]`: `"a"` (索引 2)
- `SA[1]`: `"aba"` (索引 0)
- `SA[2]`: `"ba"` (索引 1)
- `LCP[0]`: 无前一个后缀，设为 0。
- `LCP[1]`: `"a"` 和 `"aba"` 的 LCP 是 `"a"`，长度为 1。
- `LCP[2]`: `"aba"` 和 `"ba"` 的 LCP 是 `""`，长度为 0。
4. 应用公式：
验证：`"aba"` 的不同子串为 `a`, `b`, `a` (重复，不计), `ab`, `ba`, `aba`。
去重后：`a`, `b`, `ab`, `ba`, `aba`。共 5 个。正确。
不同场景下的解决方案对比表
| 场景 | 字符串特征 | 目标 | 推荐算法/公式 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|---|
| 基础数学 | 所有字符唯一 | 所有子串数（含重复实例） | |||
| 短字符串 | 任意 | 不同子串数 | 暴力枚举 + HashSet | ||
| 中等字符串 | 任意 | 不同子串数 | 哈希滚动 (Rabin-Karp) + HashSet | ||
| 长字符串 | 任意 | 不同子串数 | 后缀数组 + LCP | 或 | |
| 长字符串 | 任意 | 不同子串数 | 后缀自动机 (SAM) |
代码完成示例（Python）
以下提供两种常见达成：基础暴力法和基于后缀数组的高效法。
1 暴力法（简洁易懂）
```python
def count_distinct_substrings_brute(s: str) -> int:
n = len(s)
distinct_substrings = set()
for i in range(n):
for j in range(i + 1, n + 1):
distinct_substrings.add(s[i:j])
return len(distinct_substrings)
测试
print(count_distinct_substrings_brute("aba")) # 输出: 5 ```2 后缀数组法（高效）
```python
def count_distinct_substrings_suffix_array(s: str) -> int:
n = len(s)
# 生成后缀及其原始索引
suffixes = [(s[i:], i) for i in range(n)]
# 按字典序排序
suffixes.sort(key=lambda x: x[0])
total_substrings = n (n + 1) // 2
lcp_sum = 0
for i in range(1, n):
prev_suffix = suffixes[i-1][0]
curr_suffix = suffixes[i][0]
# 计算 LCP
lcp = 0
while lcp < len(prev_suffix) and lcp < len(curr_suffix) and prev_suffix[lcp] == curr_suffix[lcp]:
lcp += 1
lcp_sum += lcp
return total_substrings - lcp_sum
测试
print(count_distinct_substrings_suffix_array("aba")) # 输出: 5 ```常见误区与注意事项
1. 混淆“子串”与“子序列”：- 子序列的计数采用动态规划，公式为 （去重前），去重后需特殊处理。切勿将子串公式用于子序列。
- 在大多数算法题中，空子串（""）不计入总数。上述公式 默认不包含空串。如果题目要求包含，需加 1。
- 当 较大时（如 ）， 超过 32 位整数范围。在 C++/Java 中需使用 `long long` 或 `long`。
- 务必确认题目要求的是“不同内容的子串”还是“不同位置的子串”。若是后者，直接返回 即可。
总结
计算子串数目看似简单，实则蕴含了从基础组合数学到高级字符串算法的多个层次：
字符不重复：直接使用公式 。
字符重复且需去重：
小规模数据：使用 `HashSet` 暴力去重。
大规模数据：使用后缀数组 + LCP 或 后缀自动机 在 或 时间内高效求解。
掌握这些方法，不仅能解决面试中的经典问题，也为处理更复杂的字符串匹配和模式识别任务打下坚实基础。
