檢查字符串是否包含另一個字符串算法？

Question

如果我有字符串A，並且我有許多其他字符串，並且我想查看是否有任何其他字符串在A中。

什麼算法可以在儘可能少的迭代中做到這一點？

例如：

'您好，我的名字是鮑勃。'

我想看看是否包含'name is b'，它是從[11]開始的。

我不想使用正則表達式庫。

由於

Answer 1

對此最有效的算法是Aho-Corasick algorithm，其給定長度n的串並設置的總長度爲m的字符串可以找到在時間爲O所有比賽（N + M + Z），其中z是報告的總數。它基於有限自動機，是KMP string matching algorithm的推廣。

這個算法的一個很酷的方面是，如果你有一組固定的關鍵字和一堆你想要搜索的文本字符串，那麼算法可以通過O（m）預處理來加速建立匹配器。然後，您可以在時間O（n + z）中找到長度爲n的字符串中的所有匹配項。

另一方面，如果您有一個固定字符串，然後想要匹配一組不同的模式字符串，請考慮查看suffix trees，它們給出了相同的運行時間保證，但是如果文本是固定的，則速度會更快。

希望這會有所幫助！