例如:
源字符串是:“Mac 和 Jack 是 friend ” 模式字符串是:"is"。
所以看起来模式匹配总是从第 0 个索引开始。 并在源字符串中逐字符移动。
所以看起来它应该具有 O(mn) 的复杂度。 一般来说,我可以说 KMP 应该有 O(mn) 的最坏情况复杂度,但我读到使用 KMP 我们可以解决 O(m+n) 中的子串匹配算法,所以很想知道最坏情况案例分析。
最佳答案
我也在思考这个问题。这是我得出的结论。 (假设 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
^
关于algorithm - 如果模式字符串中的所有字符都是唯一/不同的,那么 KMP 如何采用 O(m+n),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44899300/