Leetcode 1967. Number of Strings That Appear as Substrings in Word

Difficulty: Easy (8 personal rank)
Keywords: Aho–Corasick algorithm

前言

這題雖然被分類為easy，但嚴格來說是非常困難的題目。字串的比對從來就不是簡單的問題，只是LC很愛將這類的問題放在easy，這題也是我在LC看到第一個適用於AC自動機的題目，因此特地將程式碼放上來。

題目

給很多patterns和一個word，問有幾個pattern有出現在word當中。

非常標準的AC自動機例題，關於AC自動機的解釋請參照我以前的文章：

• Algorithm: Aho–Corasick algorithm (AC自動機)

程式碼

• 時間複雜度：O(M + N)
• 空間複雜度：O(N)

其中N為所有patterns的全長，M為word的長度