def main(): p = "abab" s = "acbababa" print(kmp(p,s)) #求 next 数组 def buildNex(p): x=1 now=0 nex = [] nex.append(0) while x<len(p): # 如果相等 都加1 if p[now] == p[x]: x += 1 now += 1 nex.append(now) # 如果不等 且 now != 0(如果等于0 代表已经是起点,不能再找前面的公共子串了) elif now: now = nex[now-1] # now 已经移到0的位置,说明没有匹配的公共子串,x继续往后移 进行下一次匹配即可 else: nex.append(0) x += 1 return nex def kmp(p,s): tar = 0 #指向主串 pos = 0 #指向模式串 nex = buildNex(p) #获取nex数组 while tar<len(s): if p[pos] == s[tar]: pos += 1 tar += 1 elif pos: pos = nex[pos-1] else: tar += 1 if pos == len(p): #匹配成功 print(tar-pos+1) pos = nex[pos-1] # 如果没有这一步 index会超出数组范围 报错 if __name__ == '__main__': main()