string - 在多个单词中匹配一个字符串

Question

我找到了很多关于如何在字符串中匹配多个模式的解决方案，但没有找到如何在多个单词中匹配单个字符串。

到目前为止，我所知道的最好的方法是对每个单词使用 KMP 算法，但这不是很有效(复杂度 = 单词长度的总和)，所以我正在寻找一些更好的算法来这样做.

Answer 1

你从根本上误解了这个问题。您可以轻松地将问题分解为查找单词中出现的所有字符串。这是通过将每个单独的字符串组合成一个大字符串(或单词)来完成的。然后您可以遍历这个较大的字符串一次并使用有效的算法，例如 KMP 或正则表达式(虽然不一定推荐使用正则表达式)。一个例子来说明我的意思:

List<String> stringList = new ArrayList<String>();

    String first = "abc";  
    String second = "def";  
    String third = "xyz";  
    stringList.add(first);  
    stringList.add(second);  
    stringList.add(third);  

for(String string : stringList)  
{  
    kmp(string);  
} 

等同于:

List<String> stringList = new ArrayList<String>();  
stringList.add("abcdefxyz");  
for(String string : stringList)  
{  
   kmp(string);   
}  

正如 Kevin 在评论中指出的那样，在此处使用定界符可以防止生成不正确的结果。