1 背景
2 名词解释
2.1 前缀
针对模式串来说的
前缀的定义就是：包括首字母不包括尾字母的所有字串
aabaaf的前缀包括5种
a
aa
aab
aaba
aabaa
2.2 后缀
后缀也是针对模式串来说的
后缀的定义就是：包括尾字母不包括首字母的所有字串
aabaaf的后缀包括5种
2.3 最长相等前后缀
a的最长相等前后缀是0，因为它没有前缀，也没有后缀
aa的最长相等前后缀长度是1，因为前缀只有a，后缀只有a
aab的前缀有a,aa,后缀有b,ab,但是不相等，所以最长相等前后缀的长度是0.
aaba的前缀有a,aa,aab,后缀有a,ba,aba,所以最长相等前后缀是a,长度是1.
aabaa的前缀有a,aa,aab,aaba,后缀有a,aa,baa,abaa,所以最长相等前后缀是aa,长度是2.
aabaaf 的最长相等前后缀长度是0
2.4 前缀表
将上面6个串的最长相等前后缀长度连起来，就得到了前缀表
[0,1,0,1,2,0]
第一次到了f发现匹配无法完成，模式串中f前面的前缀表是2，所以意思跳到第3个位置，也就是下表为2的位置继续匹配
从哪个开始不匹配了，就找它前面字符的前缀表记录的数，是3，就从模式表的第4个位置，也就是下标为3的位置继续进行匹配操作。
实际上前缀表就是记录前面的字串前后有几个一样的。
前缀表是核心，得到了前缀表就可以继续匹配了
3 代码
3.1 创建next前缀表
记住创建next数组的过程就是整个对比的过程：
（1）现在有aaaabaacaabaf
（2）模拟代码
（3）上面模拟结果：
1次进来的时候 0
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
2次进来的时候 1
[0, 1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
3次进来的时候 2
[0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0]
4次进来的时候 3
______________不等于的时候 4 3
______________不等于的时候 4 2
______________不等于的时候 4 1
[0, 1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0]
5次进来的时候 0
[0, 1, 2, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0]
6次进来的时候 1
[0, 1, 2, 3, 0, 1, 2, 0, 0, 0, 0, 0, 0]
7次进来的时候 2
______________不等于的时候 7 2
______________不等于的时候 7 1
[0, 1, 2, 3, 0, 1, 2, 0, 0, 0, 0, 0, 0]
8次进来的时候 0
[0, 1, 2, 3, 0, 1, 2, 0, 1, 0, 0, 0, 0]
9次进来的时候 1
[0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 0, 0, 0]
10次进来的时候 2
______________不等于的时候 10 2
______________不等于的时候 10 1
[0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 0, 0, 0]
11次进来的时候 0
[0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 0, 0, 0]
12次进来的时候 0
[0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 0, 0, 0]
[0, 1, 2, 3, 0, 1, 2, 0, 1, 2, 0, 0, 0]
（4）深入理解
4.1 比较的时候相同
相等的话，就是在前面结果的基础上再次加1，就是j+=1
j就代表着s[0:i]和s[0:i+1]这两个字符串的最长共同前后缀的长度
如果上一个是4，那代表s[0:i-1]和s[0:i]这两个字符串的最长共同前后缀长度，所以接下来一样，那么就再加1
4.2 比较的时候不同
就是比较s[j]和s[i]不相同了，但是前面的是相同的，前面的前后缀表记录了前1个相同的位置，那么就不从头找，从相同的下一个开始找
比如上面的第10次比较的时候
现在有aaaabaacaabaf
s[10] = b
就看前面的模式串对应的下一个数，切记这里的j代表的是相当于模式串的模式串了，nex[j-1] 是1，
反正一直后退，一直退到它们相等，或者无处可退，也就是j=0
最终代码
# 3 完全和自己得到的时候一样
def getNext( s):
nxt = [0]*len(s)
nxt[0] = 0
j = 0 # j指向前缀，i指向后缀
for i in range(1, len(s)):
print("%d次进来的时候"%i,j)
while j > 0 and s[i] != s[j]:
print("______________不等于的时候",i,j)
j = nxt[j - 1] # 当前这个不匹配了，开始得到前一个匹配的，前一个数还不匹配就继续往前
# 这个点匹配是aabaacaabcf中的，s[8]和s[2]比较,j等于3，j一直在前面几个中，因为j代表的是开头，
# 切记：i代表的是该填充哪个位置了，j指示的是匹配到开头的哪个数了
# [0, 1, 0, 1, 2, 0, 1, 2, 3, 0, 0]
# 开始到b的时候，为什么要跳到s[1-1]=0,j等于0.就开始比较s[0]这个数了，这里理解了。
# 比较s[5]和s[2]，就是c和b比较，不等于，j 变成nxt[2-1],就是1，接着比较，就是a和c,还是不等
# 比较s[9]和s[3]，就是c和a比较，不等于，j 变成nxt[2],变成了0，为社么？
# 解释上面这个为什么？如果按咱们直观理解，s[3]就是a,不等于s[9]，那就看s[2]等于不，这就是误区
# 不能看s[2]，因为你看s[2]等于s[9],那你必须满足s[1]等于s[8]，s[0]等于s[7]，显然还得判断，因为你前面判断了s[0]等于s[6]，s[1]等于s[7]
# 所以要看nex[2],这是看能不能满足错位条件，满足了才行
if s[i] == s[j]:
j += 1
nxt[i] = j
print(nxt)
return nxt
# 4 把下面的核心算法死死背住
def next_pr(s):
nxt = [0]*len(s)
j = 0
for i in range(1,len(s)):
while j > 0 and s[i] != s[j]:
j = nxt[j-1]
if s[i] == s[j]:
j +=1
nxt[i] = j
return nxt
ss = "aabaacaabcf"
print(next_pr(ss))
3.2 结果
下面的通过了测试
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if needle == "":
return 0
def pri_table(s):
nxt = [0]*len(s)
j = 0
for i in range(1,len(s)):
while j>0 and s[i] != s[j]:
j = nxt[j-1]
if s[i] == s[j]:
j += 1
nxt[i] = j
return nxt
nxt = pri_table(needle)
j = 0
for i in range(len(haystack)):
while j > 0 and haystack[i] != needle[j]:
j = nxt[j-1]
if haystack[i] == needle[j]:
j +=1
if j == len(needle):
return (i-j+1)
return -1