Python 实现：计算仅含 a、b、c 字符串中“abc”子串与子序列的个数

以下是使用 Python 实现计算字符串中形如 `abc` 的子串和子序列个数的代码： ```python # 读取输入的字符串长度 n = int(input()) # 读取输入的字符串 s = input() # 计算形如 abc 的子串个数 substring_count = 0 for i in range(n - 2): if s[i:i + 3] == 'abc': substring_count += 1 # 计算形如 abc 的子序列个数 a_count = 0 ab_count = 0 abc_count = 0 for char in s: if char == 'a': a_count += 1 elif char == 'b': ab_count += a_count elif char == 'c': abc_count += ab_count # 输出结果 print(substring_count, abc_count) ``` 代码解释 1. 输入读取： - 第一行读取一个整数 `n`，表示字符串的长度。 - 第二行读取一个字符串 `s`。 2. 计算子串个数： - 遍历字符串 `s`，检查从每个位置开始的长度为 3 的子串是否为 `abc`。如果是，则子串计数器 `substring_count` 加 1。 3. 计算子序列个数： - 初始化三个计数器 `a_count`、`ab_count` 和 `abc_count`，分别用于记录 `a` 的个数、`ab` 子序列的个数和 `abc` 子序列的个数。 - 遍历字符串 `s` 中的每个字符： - 如果字符是 `a`，则 `a_count` 加 1。 - 如果字符是 `b`，则 `ab_count` 加上当前 `a_count` 的值，因为每个 `a` 都可以和当前的 `b` 组成一个 `ab` 子序列。 - 如果字符是 `c`，则 `abc_count` 加上当前 `ab_count` 的值，因为每个 `ab` 子序列都可以和当前的 `c` 组成一个 `abc` 子序列。 4. 输出结果： - 最后输出子串个数和子序列个数。 复杂度分析 - 时间复杂度：$O(n)$，其中 $n$ 是字符串的长度。代码只对字符串进行了一次遍历，因此时间复杂度是线性的。 - 空间复杂度：$O(1)$，只使用了常数级的额外空间。 ######[AI问答 | 574点数解答 | 2025-12-10 17:52:12]