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 在评论中指出的那样，这里使用分隔符可以防止生成不正确的结果。