数据结构——KMP算法

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()