KMP

6499 ワード
python algorithm テキストリンク

KMP

  • 一致しないテキスト文字列の前半に含まれる文字を予め指定するので、一致しない前半を再比較することなく一致
    • に一致する.
  • モードで冗長性がある場合のみ
    • が適用されます.
  • アレイnext[M]を前処理して、エラーの開始を
    • まで最小化する.
  • 時間複雑度:O(M+N)
  • テキストはabcdabcと一致し、eでは失敗シナリオモードの先頭のabcは失敗前のabcと同様に
    • を用いる.
    # T : target / P : pattern

def pre_process(P):

    M = len(P)
    lps = [0] * len(P)
    
    j = 0

    for i in range(1,M):
        if P[i] == P[j]:
            lps[i] = j + 1
            j += 1
        else:
            j = 0
            if P[i] == P[j]:
                lps[i] = j + 1
                j += 1  

    return lps


def KMP(T, P, lps):

    N = len(T)
    M = len(P)

    i, j = 0, 0
    pos = -1
    while i < N:
        if P[j] == T[i]:
            i += 1
            j += 1
        else:
            if j!= 0:
                j = lps[j-1]
            else:
                i += 1
        if j == M:
            pos = i - j
            break

    return pos

T = 'abcdabeeababcdabcef'
P = 'abcdabcef'


N = len(T)
M = len(P)
lps = pre_process(P)
print(lps)

pos = KMP(T, P, lps)
print(pos)
    ブールモルアルゴリズム
    BruteForce