尋找從字典

Question

所有子序列在一個程序中，我需要能夠有效地回答下列形式的查詢：

給定一組字符串A和查詢串Q回報所有s∈A使得s爲q的子例如，給定A = {「abc」，「aaa」，「abd」}和q =「abcd」，「abc」和「abd」應該被返回。

有沒有更好的方法比迭代A的每個元素並檢查它是否是q的子序列？

注意：我有STRIPS計劃員或自動計劃員記。 STRIPS策劃師的每個狀態都是一組命題，如{「（room rooma）」，「（at robby rooma）」，「（在ball1 rooma）」}。我想找到適用於特定州的所有地面行動。 STRIPS規劃師的行動基本上由兩部分組成，前提條件和效果（這裏並不真正相關）。先決條件是將一個行動應用到一個國家所需要的一組命題。例如，要應用一個動作「（移動rooma roomb）」，其前提條件{「（room rooma）」，「（room roomb）」，（at robby rooma）}}都必須在該狀態下爲真。

Answer 1

如果您設置一個是大，你有很多的疑問，你可以實現一個trie-like structure，其中ñ水平是指性格在字符串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; 
} 

Efectively，你將生成所有2 ^米的quesy串子集m字符，但在實踐中，trie非常稀疏，您最終會檢查更少的路徑。

速度收益來自許多查找。構建這個trie比使用暴力查找更昂貴。但是，如果您僅更新設置的唯一一個或有更新設置的手段，您將獲得良好的查找性能。

trie節點的實際數據結構取決於項目可以具有多少個可能的元素。在你的例子中，只有四個字母被使用。如果您的「字母」範圍有限，則可以使用數組。否則，你可能需要一種字典，這可能會使樹在記憶中變得很大。