查找字符串的所有“散布子字符串”

Question

我有以下问题：给定两个字符串v和w，我想将v的出现记为w的“分散子词”。下面的示例应说明该问题：让v = "aa"和w = "abaab"。然后我的问题的答案将是2，因为v发生两次：w中的位置1和3以及位置3和4。

有人知道在比顿/鼠尾草中算一个好方法吗？

谢谢！

Answer 1

有一种自然的方法可以使用dynamic programming解决此问题。

[用len(v)+1建立一个尺寸为len(w)+1的二维数组，其中dp[i][j]表示v[:i]中w[:j]的“分散子字符串”的数量。

• 最初是dp[0][j] = 1，因为每个字符串中都出现空字符串，而dp[i][0] = 0则是i > 0，因为空字符串中没有字符串。
• v[:i+1]中的w[:j+1]的分散子串要么是v[:i+1]中的w[:j]的分散子串，要么是v[i] == w[j]，也可以是v[:i]中的w[:j]的分散子串。因此，递归关系为dp[i+1][j+1] = dp[i+1][j] + (dp[i][j] if v[i] == w[j] else 0)。
• 最终结果是dp[len(v)][len(w)]。