自带的.find()方法
找字串的位置，这种事情，偷懒的话很好解决：
if not needle: return -1
return haystack.find(needle)
也算是学了学string方法。
然而也应该借此机会学一学KMP。
KMP虽然看起来代码很少，但是其中的道理还真是一时半会理不清楚的。
暴力的办法
暴力的办法很简单，对于一个给定的字符串起始位置 i ，只需要逐个比对haystack[i:i + len(haystack)]和needle是否相等就可以了。然后遍历整个range(i - len(haystack)。
但是这样的话，就存在一个问题，信息的利用太少了。
比如，ABDABC...去匹配ABDABD...，实际上，当我们匹配到第六个字母C和D不正确的时候，我们已经不必再往下匹配BDABD...了，而是可以直接匹配ABD...：
出现了不匹配：
√√√√√↓
ABDABC...
ABDABD...
√√√√√↑
暴力解法：
↓
ABDABC...
ABDABD...
↑
优化方法：
√√↓
ABDABC...
ABDABD...
√√↑
如果我们能好好整理一下这种朴素的优化逻辑，就可以提高算法的速度。这其实就是KMP算法的基本思想。
KMP算法
next数组的含义
仔细观察一下上面的例子：
√√↓
ABDABCXXX...
ABDABD...
√√↑
我们是怎样知道，可以直接移动needle到这里，而且同时知道已经有两个位是匹配了的呢？
这里就涉及了KMP算法的一个精髓部分：next数组。
首先，它将我们上面的行为总结为这个样子：
- 如果在匹配中，出现了这样的情况：
√ √ √ ↓
[A][...][A][B]
[A][...][A][C]
√ √ √ ↑
其中，[A][...][A]是经过比较，已经相同的部分；而[A]是相同的前后缀。
- 那么，我们就可以将needle前缀[A]移动到后缀[A]的地方：
√ ↓
[A][...][A][B]
[A][...]
√ ↑
然后让[B]和[...]继续进行比较。
- 例如：
√√ √ √√ ↓
[AB][D][AB][C]
[AB][D][AB][D]
√√ √ √√ ↑
我们只需移动[AB]即可：
√√ ↓
[AB][D][AB][C...]
[AB][D][AB][D...]
√√ ↑
而对于needle的每一个位，我们都可以先找出这一位之前的字串里，相等前后缀的长度，然后放入next数组，指导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数组的实现方式
首先，虽然next[i] == 0代表回溯位置是0，我们还需要约定next[0] == -1而不是0，以此作为字符串开始的标志。然后我们讨论逻辑，再讨论代码实现。
逻辑部分
初始状态
就普通的情况而言，我们的状态是这样的：
[A]X...[A]Y...
↑ ↑
p s
其中[A]是经过比较，已经相同了的部分。
X 和 Y是什么关系？
-
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
发现了吗？我们只需要将p移动到第一个[B]之后，也就是next[p]处就行了！
[B][Z...][B]X...[B][Z...][B]Y
↑ ↑
p s
然后，我们就相当于回到了开头的状态，换个字母就是[C]Z...[C]Y...。
边界条件处理
我们之所以要约定next[0] == -1，就是因为，当p == 0且X != Y的时候：
X...Y
↑ ↑
p s
根据上面的定义，我们会令p = next[0]。然而X前面已经没有字符了，所以我们需要特殊处理。当然，特判这个情况，让s += 1是可以的，但是用我们目前的约定方法，就可以套用X == Y情况的代码了。具体操作可以看看代码部分。
此外，s的遍历空间是什么呢？考虑到X == Y的情况下需要先增加s再赋值，所以应该是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] # 可以想想这个优化的意义
else:
prept = next[prept]
return next
KMP算法的本体
如果你看懂了上面关于next数组的原理，那么只需要这点代码，你大概就能知道KMP的实现方式了：
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而不挪动已经位于首端的npt。 -
if haystack[hpt] == needle[npt]就是正常的字符匹配成功。 - 为了防止你忘记，
else就是我们在next数组的含义部分的开头所说的，移动needle前缀移到相同后缀位置：
√√ ↓
[AB][D][AB][C...]
[AB][D][AB][D...]
√√ ↑
整个KMP算法到此就结束了！虽然代码很短，但是可以说非常精妙了！
有兴趣的话，可以继续了解BM算法和Sunday算法，这个链接也是讲解KMP算法的，而且图片也比较多，可以一看。
网友评论