1

最長の単一のサブシーケンスだけでなく、rubyの文字列の配列からすべての一般的なサブシーケンスを見つけようとしています。

これは、入力が

["aaaF hello"、 "aaaG hello"、 "aaaH hello"]

期待される出力は

["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より1つ短いsのすべての部分文字列を繰り返します。
  3. サブストリングごとに、配列全体に存在するかどうかを確認します。
  4. そうである場合は、結果に追加して続行します。そうでない場合は、部分文字列をsとして1に移動します。

ここに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 に答える