寻找从字典

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节点的实际数据结构取决于项目可以具有多少个可能的元素。在你的例子中，只有四个字母被使用。如果您的“字母”范围有限，则可以使用数组。否则，你可能需要一种字典，这可能会使树在记忆中变得很大。