KMS算法

KMP算法视频讲解，例子说明的很详细

#下面是找到第一次匹配的位置，如要匹配多个，修改pos的值加入循环即可
def Index_KMP(s1,s2,pos=0):
    next = get_next(s2)
    i = pos
    j = 0
    while(i < len(s1) and j < len(s2)):
        if(j == -1 or s1[i] == s2[j]):
            i += 1
            j += 1
        else:
            j = next[j]
 
    if(j >= len(s2)):
        return i - len(s2)
    else:
        return 0
 
def get_next(s2):
    i = 0
    next = [-1]
    j = -1
    while(i <len(s2)-1):
        if(j == -1 or s2[i] == s2[j]):
            i += 1
            j += 1
            next.append(j)
        else:
            j = next[j]
    return next
 
if __name__ == "__main__":
    s1 = "acabaabaabcacaabc"
    s2 = "abaabcac"
    print(Index_KMP(s1,s2))

Re正则表达式的内容以后再看 书/中国大学慕课 爬虫