KMP

字符串匹配算法
【最浅显易懂的 KMP 算法讲解】 https://www.bilibili.com/video/BV1AY4y157yL/?share_source=copy_web&vd_source=eb19190e087045161f4a9924d1e7e651

def build next(patt):
	"""
	计算Next数组
	"""
	Inext=[8]#next数组（初值元素一个0)
	prefix len=0 #当前共同前后缀的长度
	i=1
	while i<len(patt):
		if patt[prefix_len]=patt[i]:
			prefix_len += 1
			next.append(prefix_len)
			i+=1
		else:
			if prefix len =0:
				next.append(0)
				i+=1
			else:
				prefix_len = next[prefix_len - 1]
	return next

def kmp_search(string,patt):
	next=build next(patt)#假设我们已经算出了next数组（马上讲到
	i = 0#主串中的指针
	j = 0#子串中的指针
	while i<len(string):
		if string[i]=patt[j]:#字符匹配，指针后移
			i+=1
			j+=1
		elif j>0:#字符失配，根据next跳过子串前面的一些字符
			j=next[j -1]
		else:#子串第一个字符就失配
			i+=1
		if j=len(patt):#匹配成功
			return i-j