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
相应的实例：