KMP算法的跳轉容易出錯嗎？

Question

讓我們來看一個例子： 文本= 「AABCAABDCAAB」， 模式= 「AABCAAB」

在這個例子中，該模式將匹配在指數= 0
AABCAAB DCAAB
AABCAAB

根據KMP算法，當j =模式長度時，我們發現匹配和重置j = lps [模式長度-1] = 3，這意味着模式[j] ='C'

該算法由跳躍：
AABCAAB d CAAB
_____AAB Ç AAB

而不考慮跳轉之間的情況下，例如：
AABCAABDCAAB
_AABCAAB

AABCAABDCAAB
__AABCAAB
...

在這種情況下可以忽略一些比賽嗎？

Answer 1

KMP算法被證明在所有情況下都能正常工作。其背後的主要思想是，如果您匹配了模式的前k個字符，則您知道文本的k個字符，因爲它們完全匹配這些k個字符。考慮到這些k個字符的知識，計算轉換表以便在匹配k個字符時使用的轉換儘可能安全。

在你的例子中，你剛剛匹配了AABCAAB，所以你知道文本是AABCAAB。模式中只有一個C，您剛剛匹配，所以您必須將模式移動得足夠遠，以至於用於匹配的C在下一次嘗試匹配時不會與模式的任何部分重疊，在這種情況下給你下一個嘗試匹配的位置。 （我注意到KMP算法通常被描述和證明不是使模式不規則移動，而是沿着要搜索的文本有規律地步進，並計算出該模式迄今爲止匹配了多少個字符。有一個使用該算法視圖的證明，我們知道它在任何情況下都可以使用）。