algorithm - 如果模式字符串中的所有字符都是唯一/不同的，那么 KMP 如何采用 O(m+n)

Question

例如:

源字符串是:“Mac 和 Jack 是 friend ”模式字符串是:"is"。

所以看起来模式匹配总是从第 0 个索引开始。并在源字符串中逐字符移动。

所以看起来它应该具有 O(mn) 的复杂度。一般来说，我可以说 KMP 应该有 O(mn) 的最坏情况复杂度，但我读到使用 KMP 我们可以解决 O(m+n) 中的子串匹配算法，所以很想知道最坏情况案例分析。

Answer 1

我也在思考这个问题。这是我得出的结论。 (假设 n 是要搜索的字符串的长度，m 是模式的长度)

在字符串匹配的原始暴力解决方案中，您需要为给定的 m 遍历所有 n 的唯一原因是是否存在重复

例如:

string: abcdabcdabcd
pattern:abcde

迭代 1:

string: abcdabcdabcd
        ^
pattern:abcde
        ^

迭代m

string: abcdabcdabcd
            ^
pattern:abcde
            ^

不匹配!所以在 m+1 迭代中，我们做:

string: abcdabcdabcd
         ^
pattern:abcde
        ^

现在在 KMP 的情况下，在迭代 m+1 时，我们不需要将字符串指针重置到很早之前，因为如果字符串中位置 2 的字符 (1-基于索引)确实与模式匹配，那么该模式将在一行中出现重复字符。

KMP iteration m + 1, pattern has all distinct characters

string: abcdabcdabcd
            ^
pattern:abcde
        ^

如果有重复，则在迭代 m+1 时，我们不会将指针重置为 far:

KMP iteration m + 1, pattern has runs of characters

string: aaaac
            ^
pattern:aaaab
           ^