给定两个不同长度的字符串 S1 和 S2，找到 S1 和 S2 的相等子序列的数量与 S1 的最后一个字符匹配的有效方法是什么。
例如）
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]
我知道这可以使用动态编程来解决，如果有人提出有效解决这个问题的想法，那就太好了。
这基本上是一个正则表达式匹配问题。
首先让我们摆脱“最后一个字符匹配”的条件。我们希望将问题简化为“无条件的等子序列的普通数量问题”。
假设 S1="a 1 a 2 ...a n Z"。让 S1'="a 1 a 2 ...a n "。进一步假设在 S2 中有 N 次出现 Z。对于每一次出现，我们可以写
假设在 S2 中有 N 次出现 Z。对于每次出现的i，我们可以写为 S2 i ="b 1 b 2 ...b k i Zb k i +1 ..."。假设 S2'="b 1 b 2 ...b k i "。现在解决 S1' 和 S2' i的简单问题，对于 1..N 中的每个 i。
现在，如何解决简单的问题？
取较短的字符串，说它是 S1。现在让我们写它"abc…t"。将其转换为".*a?.*b?.*…t?.*". 这是你的正则表达式。您现在需要计算正则表达式匹配 S2 的方式有多少。可以使用基于 NFA 的算法来完成匹配。
要实际计算匹配数，需要了解基于 NFA 的匹配算法的内部工作原理。在任何给定时刻都有一组处于活动状态的状态。一个状态可以一分为二，或者两个状态可以合并。如果遇到错误的字符，状态可能会死亡。因此，您将 1 分分配给初始状态。当一个状态分裂时，每个新状态都会继承父级的分数。当两个状态合并时，新状态得到分数的总和。当一个国家死亡时，它的分数就会下降。
我不确定这是否与您所说的动态编程方法有什么不同。最多有 2 N个匹配项，因此在某些输入上，这将需要很长时间。
更新：看起来应该也可以直接解决“最后一个字符匹配”问题，而不是将其简化为普通问题。假设在 S2 中出现 2 次 Z：S2="ab...pZq...yZ"。（无论如何都可以忽略最后一个 Z 之后的所有字符）。可以从 S2: 构建一个正则表达式".*a?.*b?.*…p?.*(Z|Z?.*q?.*…y?.*Z)"。更多的事件以相同的方式处理。需要一个看似多余的正则表达式来维持正确的匹配数量（不仅仅是存在匹配的事实）。