如何高效统计字符串所有子串中目标子序列的出现次数？

核心思路 #

我们可以将问题转化为计算每个不重叠目标子序列实例能被多少个子串包含，最终总和就是所有实例的贡献之和。因为每个子串若包含m个不重叠实例，就会被m个实例的贡献分别计数一次，正好对应子串的贡献值。

算法步骤 #

假设原字符串为s（长度为N），目标子序列为T（长度为k，视为常数）。

1. 预处理字符位置映射

构建二维数组next_pos，其中next_pos[i][c]表示从s的第i个位置开始，字符c第一次出现的索引（不存在则记为N）。

• 初始化next_pos[N][c] = N（所有字符c）。
• 从N-1到0反向遍历s：
  • 先复制next_pos[i+1]的所有值到next_pos[i]。
  • 更新next_pos[i][s[i]] = i（当前位置的字符优先覆盖）。
    这个步骤时间复杂度为O(N*C)，C为字符集大小（如26个小写字母），属于线性级别。

2. 找出所有不重叠的目标子序列实例

按顺序遍历s，找出所有不重叠的目标子序列的起止索引：

• 初始化start = 0，空列表matches存储实例的(起始索引, 结束索引)。
• 循环：
  • 从start开始匹配T：
    • 设current = start，依次查找T的每个字符：current = next_pos[current][char]。
    • 若中途current == N，说明无法匹配，终止循环。
  • 匹配成功则将(next_pos[start][T[0]], current)加入matches，并设置start = current + 1（保证下一个实例不重叠）。
    这个步骤时间复杂度为O(m*k)，m是实例数量（最多为N/k），因k是常数，整体为线性级别。

3. 计算总贡献

遍历matches中的每个实例，计算该实例能被多少个子串包含：

• 对于实例(s_idx, e_idx)，包含它的子串的起始索引可以是0~s_idx（共s_idx+1种），结束索引可以是e_idx~N-1（共N - e_idx种）。
• 每个实例的贡献为(s_idx + 1) * (N - e_idx)，将所有实例的贡献相加即为最终结果。
  这个步骤时间复杂度为O(m)，线性级别。

示例验证 #

对于s = "jabcohnnyjohnny"，T = "johnny"：

• 预处理后找到两个实例：(0,8)和(9,14)。
• 计算贡献：(0+1)*(15-8) + (9+1)*(15-14) = 7 + 10 = 17，与示例结果一致。

时间复杂度分析 #

整体时间复杂度为O(N*C + m*k)，因C（字符集大小）和k（目标子序列长度）均为常数，实际可视为O(N)，远优于暴力法的O(N²)。

内容的提问来源于stack exchange，提问作者jp99