string - 查找字典中给定字符串的子字符串列表

Question

给定的输入基本上是一个字典(字符串数组)和一个 InputString。

我们想找出字典中该字符串的所有可能子字符串。

Input:
Dictionary:  ["hell", "hello", "heaven", "ample", "his", "some", "other", "words"]
String: "hello world, this is an example"

Output: ["hell", "hello", "his", "ample"] //all the substrings that are in dictionary.

我能想到的解决方案是从字典中构建一个类似 trie 的结构，然后运行以下循环

for(i= 0 to inputString.length)
   substring = inputString.substring(i,length)
   lookupInTrie(substring) 

lookupInTrie(string)
   this function returns list of complete words from trie that match the prefix of string. 
   i.e, if you pass in string "hello world" to this function and dictionary has word "hell" and "hello" then our lookup will return ["hell","hello"];

所以如果我们不计算dictionary->trie的转换。查找字典中给定字符串的所有子字符串可以在 O(n^2) 时间内完成。

我想知道我们是否可以进一步优化它并将复杂性从 n^2 降低。

Answer 1

您所描述的看起来是使用 Aho-Corasick string-matching algorithm 的完美地点，这本质上是您在上面描述的算法的优化版本。它的工作原理是从模式字符串构建一个特里树，然后通过它运行原始字符串，但这样做不需要大量回溯。总时间复杂度为 O(m + n + z)，其中 m 是要搜索的字符串的长度，n 是模式字符串的总长度，z 是匹配的数量。

你也可以使用 suffix tree这里。为句子构建后缀树，然后在其中搜索每个模式需要时间 O(m + n + z)，其中 m、n 和 z 的定义如上，尽管从头开始编写代码非常困难。