string - 两个字符串 S1 和 S2 的最后一个字符匹配的相等子序列数

Question

给定两个不同长度的字符串 S1 和 S2，找到 S1 和 S2 的相等子序列数且 S1 的最后一个字符匹配的有效方法是什么。

e.g)

S1 = ayb

S2 = axbxxb

在这种情况下，存在两个相等的子序列，

 "b"  => S1[2],S2[2]
 "b"  => S1[2],S2[5]
 "ab" => S1[0],S2[0] and S1[2],S2[2]
 "ab" => S1[0],S2[0] and S1[2],S2[5]

我知道这可以使用动态规划来解决，如果有人提出有效解决此问题的想法，那就太好了。

Answer 1

这基本上是一个正则表达式匹配问题。

首先让我们摆脱“最后一个字符匹配”条件。我们希望将问题简化为“不带任何条件的纯等子序列数问题”。

假设 S1="a₁a₂...a_nZ"。让 S1'="a₁a₂...a_n"。进一步假设在 S2 中有 N 次出现 Z。对于每次出现，我们都可以写

假设 Z 在 S2 中出现 N 次。对于每次出现 i 我们可以写成 S2_i="b₁b₂...b _kiZb_ki+1...”。假设 S2'="b₁b₂...b_ki"。现在解决 S1' 和 S2'_i 的简单问题，对于 1..N 中的每个 i。

现在，如何解决简单的问题？

取较短的字符串，假设它是 S1。现在让我们把它写成 "abc…t"。将其转换为 ".*a?.*b?.*…t?.*"。这是你的正则表达式。您现在需要计算正则表达式匹配 S2 的方式有多少。可以使用基于 NFA 的算法完成匹配。

要实际计算匹配次数，需要了解基于 NFA 的匹配算法的内部工作原理。有一组状态在任何给定时刻都处于事件状态。一个国家可以一分为二，或者两个国家可以合并。如果遇到错误的角色，一个国家就会死亡。因此，您将分数 1 分配给初始状态。当一个状态 split 时，每个新状态都会继承父状态的分数。当两个状态合并时，新状态获得分数之和。当一个状态死亡时，它的分数会下降。

我不确定这与您所说的动态规划方法是否有任何不同。最多有 2^N 个匹配项，因此对于某些输入，这将需要很长时间。

更新:看起来应该也可以直接解决“最后一个字符匹配”问题，而不是将其简化为普通问题。假设 Z 在 S2 中出现了 2 次:S2="ab…pZq…yZ"。 (无论如何都可以忽略最后一个 Z 之后的所有字符)。可以从 S2 构建正则表达式:".*a?.*b?.*…p?.*(Z|Z?.*q?.*…y?.*Z)"。更多的事件以相同的方式处理。需要一个看似冗余的正则表达式来维护正确数量的匹配项(而不仅仅是存在匹配项的事实)。