string - 查找可以派生字符串的不同路径的数量

Question

有一个 secret 消息，它是一个长度至少为 2 的字符串，只包含字符 A..Z。

对其应用一系列“操作”。示例中显示了一个操作。

给定最终的加密字符串，计算对源字符串使用一个或多个重复操作生成该字符串的可能方式的数量。即使它们对您的 secret 消息进行相同的加密，操作也是不同的。 IE。 : 有四种不同的方法可以从 AA 获得 AAA。

这是一个例子:

加密后的字符串是:ABABA。输出将是:8。以下是您可以产生 ABABA 的不同方式:

1. 从 AB 开始 -> AB+A -> AB+ABA
2. 从 AB 开始 -> AB+A -> ABA+BA3.从ABA开始 -> AB+ABA
3. 从 ABA 开始 -> ABA+BA
4. 从 BA -> A+BA -> AB+ABA 开始
5. 从 BA -> A+BA -> ABA+BA 开始
6. 从 ABAB 开始 -> ABAB+A
7. 从 BABA 开始 -> A+BABA

你能帮忙推荐一个算法来解决这个问题吗？我考虑过尝试递归，但在更大的输入上我的代码运行速度很慢。

Answer 1

请注意，在推导的每一步，您都会得到“加密”字符串的一个子字符串。有很多(即 O(n^2))这样的子串。

您可以找到从每个后缀和前缀直接导出最终字符串的方法的数量。

因此，您有很多可能的子问题，您可以将一个问题分解为一组完整的子问题，对每个子问题进行计数，然后将结果相加。

通过只解决每个子问题一次，您可以从中得到一个动态规划算法。该动态规划算法可以在立方时间内运行。