1

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

这意味着如果输入是

[“aaaF 你好”，“aaaG 你好”，“aaaH 你好”]

预期的输出是

[“aaa”，“你好”]

我一直在搞乱最长的单子序列算法，但不知道如何获得适当的输出。大多数方法的问题是它们在最终数组中还有其他元素，例如“a”、“aa”、“h”、“he”、“hel”、“hell”

4

2 回答 2

1

好吧，像“a”和“aa”这些较小的子序列是常见的子序列，所以这不会是不正确的。

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

这可以通过（在伪代码中）完成

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);
   }
}

祝你好运！

于 2011-11-16T08:24:30.110 回答
0
  1. 从数组中选择一个字符串 s。
  2. 迭代 s 的所有比 s 短 1 的子串。
  3. 对于每个子字符串，检查它是否存在于整个数组中。
  4. 如果是，则将其添加到结果中并继续。如果不是，则转到 1，子字符串为 s。

继承人python/pseudo中的一些代码：

A = String["aaaf hello","aaag hello"]

def find(s):
   res = []
   for sub in [s[1:],s[:-1]]
     if sub in all items in A:
       res.append(sub)
     else:
       res.append(find(sub))
   return res
于 2011-11-16T08:18:18.003 回答