ruby - 字符串数组中的所有公共(public)子序列

Question

我试图在 ruby​​ 中的字符串数组中找到所有常见的子序列而不仅仅是最长的单个子序列。

这意味着如果输入是

["aaaF hello", "aaaG hello", "aaaH hello"]

预期的输出是

["aaa", " hello"]

我一直在研究最长的单个子序列算法，但无法弄清楚如何获得适当的输出。大多数方法的问题是它们在最终数组中有其他元素，如“a”、“aa”、“h”、“he”、“hel”、“hell”

Answer 1

嗯，这些较小的子序列，如“a”和“aa”是常见的子序列，所以这不会是错误的。

如果你真的只想要最长的公共(public)子序列(即那些不包含在任何其他公共(public)子序列中的子序列)，你需要做的是检查这些子序列是否是更大的公共(public)子序列的一部分，如果是，则丢弃它们。

这可以通过(伪代码)完成

finalsubsequences = copy(subsequences);
for(subseq in subsequences) {
   for(subseq2 in subsequences) {
       if(subseq2.indexOf(subseq) != false)
       // subseq contains subseq2, thus discard subseq2
       finalsubsequences.remove(subseq2);
   }
}

祝你好运!