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

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); 
} 

正如凯文在评论中指出，使用一个分隔符的位置会防止产生不正确的结果。