转载

KMP算法

#递归求next数组
def next(p):
    nextArr = [0 for i in range(len(p))]

    #规定 next[0] == -1
    nextArr[0] = -1

    j, k = 0, -1

    while(j < len(p)-1):
        if k == -1 or p[j] == p[k]:
            j += 1
            k += 1
            nextArr[j] = k
        else:
            k = nextArr[k]

    return nextArr
    
def KMP(string, p):

    nextArr = next(p)

    print (nextArr)

    #字符串指针,子串指针
    i, j, n, m = 0, 0, len(string), len(p)

    while i < n:

        while j < m:
            if p[j] == string[i]:
                j += 1; i += 1;
            else:
                break

        if j == m: 
            print ("字符串在%s处匹配" % str(i-m))
            return

        if nextArr[j] == -1:
            i += 1

        else:
            j = nextArr[j]

    return -1

if __name__ == '__main__':
    KMP('ababxbababcadfdsss', 'abcad')
正文到此结束
本文目录