KMP匹配字符串时，如果匹配字符失败了，并不从头再匹配，而是回溯到一个特定的位置，这个位置和需要匹配的字符串有关，用next数组记录匹配每个位置失败时要回溯的位置。这样就能减少回溯和匹配的次数，从而提高计算效率。
计算next数组：
def GetNext(s:str)->list:
n = len(s)
k = 0
Next = [-1]#首个匹配失败会返回-1
for i in range(1,n):#从第二个字符开始匹配
Next.append(k)#s[i]匹配失败就回溯到s[k],再开始匹配
while k!=-1 and s[k]!=s[i]:#如果s[k]和s[i]相同,那么k无需回退
k = Next[k]#如果不同,将k回退到s[k]匹配失败要回退的位置,直到k==-1，或者s[k]==s[i]
k+=1
return Next
这个过程就像需要0匹配的字符串自己和自己匹配，也叫字符串的自匹配。
下面举个例子：
然后是kmp比较的函数：
def KmpLocation(s1:str,s2:str)->int:#s1为大字符串,s2位要被匹配的字符串
Next = GetNext(s2)
n = len(s1)-len(s2)#字符串长度的差
j = 0
for i in range(0,len(s1)+1):
if j == len(s2):#j指到s2的最后一个字符后面表示匹配成功
return i-j#返回匹配成功时s1的相应索引
if i==len(s1):#i已经指到了s1的最后一个字符串，但是j还没到s2的最后一个字符串
return -1#匹配失败
while j!=-1 and s1[i]!=s2[j]:
j = Next[j]
j+=1
相应的实例：
