C++ 不同子序列

在计算机科学领域，特别是在字符串处理和组合学中，不重复子序列的概念占有重要地位。子序列是通过删除字符串中的零个或多个字符而不改变剩余字符顺序而派生的。查找字符串中不重复子序列的问题很有趣，在生物信息学、文本处理和编码理论等各种领域都有应用。

重要性和应用

在生物信息学中，需要分析 DNA 序列，因此计算不重复子序列的问题至关重要。例如，研究人员可能对查找给定 DNA 链可以形成的所有可能的独特序列感兴趣。这有助于理解遗传变异和进化关系。在文本处理中，这一概念对于数据压缩等任务很有用，目标是通过识别和删除冗余模式来最大限度地减少存储空间。编码理论也利用这个问题来创建有效的纠错码和加密算法。

计算不重复子序列的主要挑战在于有效地管理和跟踪在每个步骤形成的子序列，尤其是在输入字符串长度增加时。生成所有可能的子序列然后过滤重复项的朴素方法计算成本很高，对于长字符串来说是不可行的。

动态规划为解决这个问题提供了一种更有效的方法。通过将问题分解为更小的子问题并存储这些子问题的结果，动态规划可以减少冗余计算。这种方法确保每个子序列仅被计算一次，从而优化了过程。

方法 1：计算不重复子序列的暴力方法

计算字符串中不重复子序列的暴力方法很简单，但效率极低。这种方法涉及生成字符串的所有可能子序列，然后计算唯一子序列。虽然概念上很简单，但由于可能的子序列数量呈指数增长，因此该方法的实用性会随着字符串长度的增加而迅速降低。

字符串的子序列是通过删除零个或多个字符而不改变剩余字符的顺序形成的。例如，字符串“abc”的子序列是“”，“a”，“b”，“c”，“ab”，“ac”，“bc”和“abc”。暴力方法显式生成所有这些子序列，然后计算不重复子序列。这可以使用递归或位操作来完成。

程序

输出

 
Enter a string: ab
The number of distinct subsequences is: 3   

说明

提供的代码使用暴力方法解决了计算字符串中不重复子序列的问题。该解决方案结构化为多个类，以提高清晰度和模块化，每个类都有特定的职责。以下是代码的详细说明：

• SubsequenceGenerator 类
  目的
  SubsequenceGenerator 类负责生成给定字符串的所有可能子序列。
  成员
  私有成员
  Str：一个字符串，代表要生成其子序列的输入。
  Subsequences：一个集合，用于存储唯一的子序列，确保不计算重复项。
  方法
  公共方法
  SubsequenceGenerator(const string& input)：初始化输入字符串 str 的构造函数。
  generateAllSubsequences()：此方法通过调用私有辅助方法 generateSubsequences 来启动生成所有子序列的过程。
  getUniqueSubsequences()：返回生成的唯一子序列的集合。
  私有方法
  generateSubsequences(int index, string current)：一个递归辅助方法，用于构造子序列。它接受两个参数：index，用于跟踪字符串中的当前位置；current，用于累积正在形成的当前子序列。
  基本情况：如果 index 到达字符串的长度，则将当前子序列（存储在 current 中）插入 subsequences 集合中，然后函数返回。
  递归情况
  排除当前字符：函数在不将当前字符添加到 current 的情况下，使用 index + 1 调用自身。
  包含当前字符：函数使用 index + 1 调用自身，将当前字符添加到 current。
• DistinctSubsequencesCounter 类
  目的
  DistinctSubsequencesCounter 类负责利用 SubsequenceGenerator 来计算输入字符串的不重复子序列的数量。
  成员
  私有成员
  Generator：SubsequenceGenerator 类的一个实例，使用输入字符串进行初始化。
  方法
  公共方法
  DistinctSubsequencesCounter(const string& input)：构造函数，使用输入字符串初始化生成器。
  countDistinctSubsequences()：此方法协调计数过程。它首先调用generateAllSubsequences来生成所有子序列。然后使用 getUniqueSubsequences 检索唯一子序列，并返回此集合的大小减去 1，以排除空子序列。
• 主函数
  目的
  main 函数充当程序的入口点。它与用户交互，管理输入/输出，并演示 DistinctSubsequencesCounter 的功能。
  步骤：
  输入处理：程序提示用户输入一个字符串，该字符串被读取并存储在变量 input 中。
  对象创建：创建 DistinctSubsequencesCounter 的实例，并使用用户提供的字符串对其进行初始化。
  计算不重复子序列：在 counter 对象上调用 countDistinctSubsequences 方法来计算不重复子序列的数量。
  输出：结果（不包括空子序列的不重复子序列的数量）将打印到控制台。

复杂度分析

时间复杂度

所提供程序的时序复杂度主要由子序列的递归生成及其插入到集合中的操作驱动。

子序列生成

generateSubsequences 函数被递归调用以生成输入字符串的所有可能子序列。对于长度为 n 的字符串，每个字符都有两个选择：包含在当前子序列中或排除。这导致了 2^n 个可能的子序列。

因此，递归调用的总数为 2^n，导致指数时间复杂度 O(n^2)

集合插入

递归生成的每个子序列都将被插入到集合中。将元素插入集合通常需要O(log k) 时间，其中 k 是集合中当前元素的数量。

由于我们正在插入2^n个子序列，因此插入的总时间为 O(log n)。结合这两个组成部分，总体时间复杂度主要由子序列的指数生成决定，结果为O(n.2^n)。

空间复杂度

空间复杂度涉及递归函数调用堆栈使用的空间以及集合中存储唯一子序列所需的空间。

递归调用堆栈

递归树的深度为 n，对应于输入字符串的长度。在递归的每个级别，都会形成一个新的子序列并传递。因此，递归树的最大深度为 n，导致调用堆栈的空间复杂度为 O(n)。

集合存储

subsequences 集合存储所有生成的唯一子序列。在最坏的情况下，所有子序列都唯一，集合将包含2^n 个子序列。

所有子序列的总长度也是一个因素。平均而言，考虑到子序列的长度从 0 到 n 不等，子序列的平均长度约为 n/2。因此，存储所有子序列所需的总空间为O(n.2^n)。

辅助空间

除了集合和递归堆栈之外，其他辅助空间包括输入字符串 str、当前子序列 current 和索引等变量。这些总共占用 O(n) 空间，与集合所需的指数空间相比微不足道。

将这些组成部分结合起来，总体空间复杂度为O(2^n)。这是因为集合中存储的子序列数量呈指数增长，每个子序列都需要与其长度成比例的空间。

方法 2：动态规划方法

动态规划（DP）方法通过利用表来存储中间结果来优化计算不重复子序列的过程。此方法通过将问题分解为更小的子问题并组合其结果来系统地构建解决方案。这确保每个子序列都被精确地计算一次，并避免重复计算。

在此方法中，创建了一个 DP 数组 dp，其中 dp[i] 表示子字符串 s[0...i-1] 的不重复子序列的数量。数组初始化为 dp[0] 设置为 1，表示空子序列。使用映射来跟踪每个字符的最后一次出现，这有助于防止重复计算包含先前出现过的字符的子序列。

随着算法遍历字符串，它通过考虑包含和排除当前字符的子序列来更新 dp 数组。如果一个字符先前出现过，则会减去其最后一次出现之前的子序列数量，以避免重复。这确保每个子序列都是唯一的。

存储在 dp[n]（其中 n 是输入字符串的长度）中的最终结果表示不重复子序列的总数，不包括空子序列。DP 方法将时间复杂度从指数级别显著降低到多项式级别，使其对于更长的字符串来说效率更高。

程序

输出

 
Choose an option:
1. Process a single string
2. Process multiple strings
Enter your choice (1 or 2): 1
Enter a string: abaa
The number of distinct subsequences is: 9
Do you want to process more strings? (y/n): n   

说明

提供的代码旨在计算给定字符串中不重复子序列的数量，采用动态规划方法。代码结构化为处理单个和多个字符串输入，并组织成多个函数以提高模块化和可读性。以下是代码各部分的详细说明：

• 包含和命名空间
  代码包括标准库，如用于输入和输出操作的 <iostream>，用于处理字符串的 <string>，用于高效键值存储的 <unordered_map>，以及用于动态数组操作的 <vector>。使用 namespace std 指令允许代码在不需要用 std:: 前缀的情况下使用标准库组件。
• countDistinctSubsequences 函数
  此函数是程序的核心，负责使用动态规划计算给定字符串中不重复子序列的数量。
  初始化
  确定字符串的长度 n。
  初始化一个大小为 n + 1 的向量 dp，所有元素都设置为 0。此向量将存储 s 的每个子字符串的不重复子序列的数量。初始化一个无序映射 last_occurrence 以跟踪字符串中每个字符的最后一次出现。
  基本情况
  dp[0] 设置为 1，表示基本情况，即空字符串的不重复子序列数量为 1（即空子序列本身）。
  DP 数组更新
  循环遍历字符串的每个字符，从索引 1 到 n。对于位置 i 的每个字符，dp[i] 更新为 2 * dp[i - 1]。这考虑了所有包含当前字符的子序列以及所有不包含当前字符的子序列。
  从字符串中检索当前字符，如果该字符以前出现过（通过最后一次出现检查），则从 dp[i] 中减去过计的子序列。这是通过减去 dp[lastIdx - 1] 来完成的，其中 lastIdx 是当前字符的最后一次出现。
  在 lastOccurrence 映射中更新当前字符的最后一次出现。
  结果计算
  函数返回 dp[n] - 1，其中 n 是输入字符串的长度。这会从总计数中减去空子序列。
• processMultipleStrings 函数
  此函数处理多个字符串输入，并使用 countDistinctSubsequences 函数进行处理。
  输入处理
  函数提示用户输入要处理的字符串数量。然后它从用户那里读取每个字符串，并将它们存储在字符串向量中。
  处理每个字符串
  函数遍历字符串向量，为每个字符串调用 countDistinctSubsequences 来计算不重复子序列的数量。为每个字符串打印结果。
  getInputString 函数
  此实用函数处理从用户那里输入单个字符串。它只是提示用户输入一个字符串并返回输入字符串。
• 主函数
  main 函数将所有内容整合在一起，并提供一个用于选择不同处理选项的用户界面。
  用户输入菜单
  向用户显示菜单，允许他们选择处理单个字符串或多个字符串。
  根据用户的选择，main 函数会调用 getInputString 和 countDistinctSubsequences 来处理单个字符串，或者调用 processMultipleStrings 来处理多个字符串。
  重复选项
  在处理完所选选项后，会询问用户是否要处理更多字符串。如果用户输入“y”或“Y”，则会再次显示菜单，允许重复进行字符串处理。

复杂度分析

时间复杂度

计算字符串中不重复子序列的动态规划方法的时间复杂度主要由 countDistinctSubsequences 函数主循环内的操作决定。

初始化

函数首先初始化变量和数据结构。此步骤需要恒定时间，O(1)。

DP 数组构建

主要计算发生在循环中，该循环遍历字符串 s 的每个字符。此循环从 i=1 到 i=n 运行，其中 n 是字符串的长度。

在每次迭代中

更新 dp 数组包括基本算术运算（dp[i] = 2 * dp[i - 1]）以及可能访问/修改 lastOccurrence 映射中的条目。

在 lastOccurrence 映射（一个无序映射）中检查和更新条目平均需要 O(1) 时间。

因此，循环的每次迭代需要 O(1) 的算术运算时间和 O(1) 的平均映射操作时间，每次迭代的复杂度为O(1)。

由于循环迭代 n 次，构建 dp 数组的总时间复杂度为O(n)。

结果计算

构建 dp 数组后，函数返回 dp[n] - 1，其中 n 是输入字符串 s 的长度。此最终计算在恒定时间O(1)内完成。

总体时间复杂度

将所有操作放在一起考虑，countDistinctSubsequences 函数的总体时间复杂度由 O(n) 的 dp 数组构建复杂度决定。

因此，使用此动态规划方法计算长度为 n 的字符串中不重复子序列的时间复杂度为 O(n)。

空间复杂度

动态规划方法的时间复杂度涉及用于存储中间结果和管理附加信息的数据结构所占用的空间。

DP 数组

dp 数组的大小为 n+1，其中 n 是输入字符串 s 的长度。此数组存储每个子字符串的不重复子序列的数量，需要O(n)空间。

最后出现映射

lastOccurrence 无序映射用于跟踪字符串 s 中每个字符的最后一次出现索引。在最坏的情况下，如果所有字符都唯一，则此映射最多可以存储 n 个条目（对于长度为 n 的字符串），每个条目平均需要 O(1)空间。

因此，lastOccurrence 映射的空间复杂度在最坏情况下为 O(n)。

附加空间

除了 dp 数组和最后一次出现映射之外，函数还使用几个额外的变量用于索引和字符存储，这些变量占用恒定空间，O(1)。

总体空间复杂度

将所有空间需求合并起来，长度为 n 的字符串中不重复子序列的动态规划方法的总空间复杂度为O(n)。

此 O(n) 空间复杂度主要归因于 dp 数组和lastOccurrence映射的存储要求。