正在搜索单词中是否包含trie集

Question

假设我有两套：

Set A: ['hi', 'there', 'hire', 'hih', 'hih543']
Set B: ['hihow', 'himan, 'fsdko45']

现在，这些集合在现实中每一个都包含近百万个元素。

简而言之，我需要做的是过滤集合B，以这种方式

1) 对于集合B的每个元素，找到集合A中为其前缀的所有元素

所以在上面的例子中，当我对照hihow检查集合A时，我得到两个结果：hi和hih。

2) 假设我有max_offset = 3。对于我在集合A中得到的每个结果，我应该将[0,1,2,3]添加到集合A元素长度，如果结果中的任何一个等于集合B元素长度，则返回true。

在这个例子中，假设我们从hih开始，所以我给它加上"1"，加上"2"，得到一个匹配，hih.size + 2 == hihow.size。整个操作返回true。

现在，我如何才能做到这一点，而不需要等待数小时才能完成此操作？我想我可以使用的一种方法是尝试1盘。假设我们使集合B a尝试允许快速查找。

现在，我对集合A的元素进行迭代，并检查：对于集合B的哪些元素，这个元素是前缀？所以对于'hi'，我会得到['hihow', 'himan']。现在我将[0,1,2,3]添加到hi.size，如果结果与数组中任何一个元素的大小匹配，则该元素就是匹配的。

另一种方法是使集合A尝试，并在集合B上迭代，在其末尾去掉0-3个字符。所以说，我取hihow，我产生['hihow', 'hiho', 'hih']，并检查所有三个字符是否与集合A尝试匹配。是的，有一场比赛，所以这是真的。

恐怕我在这种方法的正确性方面有所欠缺，所以我把它贴在了这里。此外，如果有人有更简单/更好的方法，请告诉我。谢谢

Answer 1

使用此gem，查找以前缀开头的单词似乎比查找包含在单词中的前缀更容易。

Trie从集合B完成。对于每个匹配，此代码检查后缀是否最多有3个字符：

# gem install triez
require 'triez'
prefixes = ['hi', 'there', 'hire', 'hih', 'hih543']
words =  ['hihow', 'himan', 'fsdko45']
word_trie = Triez.new
words.each do |word|
word_trie[word] = 1
end
prefixes.each do |prefix|
suffixes = word_trie.search_with_prefix(prefix).select{|suffix, id| suffix.size <=3 }
suffixes.each do |suffix, id|
word = prefix + '|' + suffix
puts word
end
end
# =>
# hi|man
# hi|how
# hih|ow