教培參考
教育培訓(xùn)行業(yè)知識(shí)型媒體
發(fā)布時(shí)間: 2024年12月28日 11:49
kmp模式匹配算法
kmp模式匹配算法由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人們稱它為克努特—莫里斯—普拉特操作(簡(jiǎn)稱KMP算法)。KMP算法的核心是利用匹配失敗后的信息，盡量減少模式串與主串的匹配次數(shù)以達(dá)到快速匹配的目的。具體實(shí)現(xiàn)就是通過一個(gè)next()函數(shù)實(shí)現(xiàn)，函數(shù)本身包含了模式串的局部匹配信息。KMP算法的時(shí)間復(fù)雜度O(m+n)。
KMP算法是三位學(xué)者在 Brute-Force算法的基礎(chǔ)上同時(shí)提出的模式匹配的改進(jìn)算法。Brute- Force算法在模式串中有多個(gè)字符和主串中的若干個(gè)連續(xù)字符比較都相等,但最后一個(gè)字符比較不相等時(shí),主串的比較位置需要回退。KMP算法在上述情況下,主串位置不需要回退,從而可以大大提高效率。
溫馨提示：
