自帶的.find()方法
找字串的位置，這種事情，偷懶的話很好解決：
if not needle: return -1
return haystack.find(needle)
也算是學(xué)了學(xué)string方法贾铝。
然而也應(yīng)該借此機會學(xué)一學(xué)KMP吼拥。
KMP雖然看起來代碼很少，但是其中的道理還真是一時半會理不清楚的褪尝。
暴力的辦法
暴力的辦法很簡單亏推，對于一個給定的字符串起始位置 i ，只需要逐個比對haystack[i:i + len(haystack)]和needle是否相等就可以了叁巨。然后遍歷整個range(i - len(haystack)斑匪。
但是這樣的話，就存在一個問題锋勺，信息的利用太少了蚀瘸。
比如，ABDABC...去匹配ABDABD...庶橱，實際上贮勃，當我們匹配到第六個字母C和D不正確的時候，我們已經(jīng)不必再往下匹配BDABD...了悬包，而是可以直接匹配ABD...：
出現(xiàn)了不匹配：
√√√√√↓
ABDABC...
ABDABD...
√√√√√↑
暴力解法：
↓
ABDABC...
ABDABD...
↑
優(yōu)化方法：
√√↓
ABDABC...
ABDABD...
√√↑
如果我們能好好整理一下這種樸素的優(yōu)化邏輯衙猪，就可以提高算法的速度。這其實就是KMP算法的基本思想布近。
KMP算法
next數(shù)組的含義
仔細觀察一下上面的例子：
√√↓
ABDABCXXX...
ABDABD...
√√↑
我們是怎樣知道垫释，可以直接移動needle到這里，而且同時知道已經(jīng)有兩個位是匹配了的呢撑瞧？
這里就涉及了KMP算法的一個精髓部分：next數(shù)組棵譬。
首先，它將我們上面的行為總結(jié)為這個樣子：
- 如果在匹配中预伺，出現(xiàn)了這樣的情況：
√ √ √ ↓
[A][...][A][B]
[A][...][A][C]
√ √ √ ↑
其中订咸，[A][...][A]是經(jīng)過比較，已經(jīng)相同的部分酬诀；而[A]是相同的前后綴脏嚷。
- 那么，我們就可以將needle前綴[A]移動到后綴[A]的地方：
√ ↓
[A][...][A][B]
[A][...]
√ ↑
然后讓[B]和[...]繼續(xù)進行比較瞒御。
- 例如：
√√ √ √√ ↓
[AB][D][AB][C]
[AB][D][AB][D]
√√ √ √√ ↑
我們只需移動[AB]即可：
√√ ↓
[AB][D][AB][C...]
[AB][D][AB][D...]
√√ ↑
而對于needle的每一個位父叙，我們都可以先找出這一位之前的字串里，相等前后綴的長度肴裙，然后放入next數(shù)組趾唱，指導(dǎo)KMP核心算法指針的回溯位置。
比如：
對于'ABDABD...'
>> next[3] == ?
[][ABD][][A...]
因此next[3] == 0
>> next[4] == ?
[A][BD][A][B...]
因此next[4] == 1
>> next[5] == ?
[AB][D][AB][D...]
因此next[5] == 2
next數(shù)組的實現(xiàn)方式
首先蜻懦，雖然next[i] == 0代表回溯位置是0甜癞，我們還需要約定next[0] == -1而不是0，以此作為字符串開始的標志宛乃。然后我們討論邏輯悠咱，再討論代碼實現(xiàn)蒸辆。
邏輯部分
初始狀態(tài)
就普通的情況而言，我們的狀態(tài)是這樣的：
[A]X...[A]Y...
↑ ↑
p s
其中[A]是經(jīng)過比較乔煞，已經(jīng)相同了的部分吁朦。
X 和 Y是什么關(guān)系？
-
X == Y渡贾，則p, s都向前移動逗宜，next[s] = len([AX])，也就是next[s] = p空骚。
[AX]Z...[AY]Q...
↑ ↑
p s
-
X != Y纺讲，那么我們將[A]展開看看：
[B][Z...][B]X...[B][Z...][B]Y
↑ ↑
p s
發(fā)現(xiàn)了嗎？我們只需要將p移動到第一個[B]之后囤屹，也就是next[p]處就行了熬甚！
[B][Z...][B]X...[B][Z...][B]Y
↑ ↑
p s
然后，我們就相當于回到了開頭的狀態(tài)肋坚，換個字母就是[C]Z...[C]Y...乡括。
邊界條件處理
我們之所以要約定next[0] == -1，就是因為智厌，當p == 0且X != Y的時候：
X...Y
↑ ↑
p s
根據(jù)上面的定義诲泌，我們會令p = next[0]。然而X前面已經(jīng)沒有字符了铣鹏，所以我們需要特殊處理敷扫。當然，特判這個情況诚卸，讓s += 1是可以的葵第，但是用我們目前的約定方法，就可以套用X == Y情況的代碼了合溺。具體操作可以看看代碼部分卒密。
此外，s的遍歷空間是什么呢棠赛？考慮到X == Y的情況下需要先增加s再賦值哮奇，所以應(yīng)該是range(len(needle) - 1)。
代碼部分
def calNext(needle):
prept = -1
sufpt = 0
nlen = len(needle)
next = [-1] * nlen
while sufpt < nlen - 1:
if prept == -1 or needle[prept] == needle[sufpt]:
prept += 1
sufpt += 1
if needle[prept] != needle[sufpt]:
next[sufpt] = prept
else:
next[sufpt] = next[prept] # 可以想想這個優(yōu)化的意義
else:
prept = next[prept]
return next
KMP算法的本體
如果你看懂了上面關(guān)于next數(shù)組的原理恭朗，那么只需要這點代碼，你大概就能知道KMP的實現(xiàn)方式了：
hpt = npt = 1
while hpt < hlen and npt < nlen:
if npt == -1 or haystack[hpt] == needle[npt]:
hpt += 1
npt += 1
else:
npt = next[npt]
if patpt == plen: return strpt - patpt
else: return -1
-
if hpt == -1和next部分的算法一樣依疼，是為了挪動hpt而不挪動已經(jīng)位于首端的npt痰腮。 -
if haystack[hpt] == needle[npt]就是正常的字符匹配成功。 - 為了防止你忘記律罢，
else就是我們在next數(shù)組的含義部分的開頭所說的膀值，移動needle前綴移到相同后綴位置：
√√ ↓
[AB][D][AB][C...]
[AB][D][AB][D...]
√√ ↑
整個KMP算法到此就結(jié)束了棍丐！雖然代碼很短，但是可以說非常精妙了沧踏！
有興趣的話歌逢，可以繼續(xù)了解BM算法和Sunday算法，這個鏈接也是講解KMP算法的翘狱，而且圖片也比較多秘案，可以一看。
