辞書アルゴリズムからすべての部分列を見つける

プログラムでは、私は次の形式のクエリに効率的に答える必要があります：

文字列Aとクエリ文字列qの集合が与えられれば、sがqの部分列であるようなすべてのs∈Aを返す たとえば、A = {"abc"、 "aaa"、 "abd"}、q = "abcd"の場合、 "abc"と "abd"を返す必要があります。

Aの各要素を反復し、それがqの部分列であるかどうかを確認するよりも良い方法はありますか？

注意： 私はSTRIPSプランナーまたは自動プランナーを念頭に置いています。 STRIPSプランナーの各州は{"（room rooma）"、 "（at-robby rooma）"、 "（ball1 rooma）"などの一連の命題です。私は、特定の状態に適用可能な全ての根本的な行動を見つけたいと思っています。 STRIPSプランナのアクションは基本的に前提条件と効果の2つの部分から成っています（ここでは実際には関係ありません）。前提条件は、州に行動を適用するために必要な命題のセットです。たとえば、 "move rooma roomb"というアクションを適用するには、その前提条件、{"（room rooma）、"（room roomb） "、"（at robby rooma）} "がすべてtrueでなければなりません。

回答：

あなたのセット A 大規模でクエリが多い場合は、 トライ様構造、レベル n 文字を指す n 文字列であなたの例では：

trie = {
a: {
a: {
a: { value: "aaa"}
},
b {
c: { value: "abc"},
d: { value: "abd"}
}
}
}

そうすれば、トライで分岐したパスでマッチを検索することができます：

function query(trie, q) {
s = Set();

if (q.isEmpty()) {
if (trie.value) s.add(t.value);
} else {
s = s.union(query(trie, q[1:]));

c = substr(q, 0, 1);
if (t[c]) {
s = s.union(query(t[c], substr(q, 1));
}
}
return s;
}

効果的に、あなたはすべての2 ^m の狭い列の部分集合 m 実際には、トライは疎であり、最終的にパスの数を減らすことになります。

スピード・ペイオフには多くのルックアップがあります。 トライの構築は、ブルートフォースルックアップを行うよりもコストがかかります。しかし、トライを1つだけ作成するか、セットを更新するときにトライを更新する手段があれば A、あなたは良いルックアップのパフォーマンスを得るだろう。

トライノードの実際のデータ構造アイテムが持つ可能性のある要素の数によって異なります。あなたの例では、4文字しか使用されていません。限られた範囲の「文字」がある場合は、配列を使用できます。さもなければあなたは辞書を必要とするかもしれません、それは木をメモリでかなり大きくするかもしれません。