在多個單詞中匹配一個字符串

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

正如凱文在評論中指出，使用一個分隔符的位置會防止產生不正確的結果。