[Algorithm]KMPアルゴリズム(Python)

KMPアルゴリズムとは?

アイデア悩み

LPSアレイ

KMPアルゴリズム

KMPアルゴリズムとは?
Knuth-Morris-Prattアルゴリズム(KMP)は、文字列内の特定の単語(パターン)を効率的に検索できる文字列検索アルゴリズムです.
例えば、下図に示すページ検索機能です.

2.創意的な悩み
逐字比較
これは低効率な方法です.次の写真には文章が少ないが、数億の単語の中で単語を見つけるには多くの労働が必要だ.
時間複雑度はO(nm)であった.
O(検索する文*検索する単語)

3.LPS方案
まず、KMPアルゴリズムでは、文字の接頭辞がどれほど似ているかを表す数値配列が必要である.その案がLPS案です.
簡単に言えば、文を見つけるパターンです.LPSアレイは、効率的なKMPアルゴリズムを実現するのに役立ちます.
難しくないです.次の手順に従ってください.
👉 Step 1(「aaa」のLPSアレイ)
Jと単語(「aaa」)を使用してLPSアレイを検索しましょう.
スタート:スタート
1:現在のjの位置文字:“a”と現在の文字:“a”を比較します.(a=a)に等しい場合、jは前の1つに送信される(->).
1-1:jの位置を現在位置にします.

2:現在のjの位置文字を比較する:“a”と現在の文字:“a”.(a=a)に等しい場合、jは前の1つに送信される(->).
2−2:jの位置を現在位置にする.

👉 Step 2
Jと単語(「aab」)を使用してLPSアレイを検索しましょう.
1:現在のjの位置文字:aを現在の文字:bと比較する場合、j位置をj-1のLPS配列値:0に対応する単語:aと比較する.
2:違うので0を加えます.
!! 現在の文字に一致する文字またはjが0番目のセルに移動するまで!

練習する.
「aabaacd」を使って練習してみましょう.

[0,1,2,2,0,1,2,3,0]などのLPSスキームが得られた.
コード#コード#

target = "aaabaaac"
    
# LPS 배열
def getLpsArray (target):
    lpsArray = [0]

    i = 1
    j = 0

    while(i < len(target)):
        
        if(target[i] == target[j]): # 같다면 j 를 한 칸 앞( -> )으로 보내줍니다.
            j += 1
            i += 1
            lpsArray.append(j)
        else: # 같지 않다면 현재 문자와 일치하는 문자가 나타나거나 j 가 0번째 칸으로 갈 때까지 이동합니다.
            if(j > 0):
                j -= 1
            elif(j == 0):
                lpsArray.append(0)
                i += 1

    return lpsArray

4.KMPアルゴリズム
次の例では、これらの原理を示します.
KMPアルゴリズムの時間的複雑度はO(N＋M)であった.
O(検索する文+検索する単語)
私は「aabaac」で「aabaacd」を探しています.
に道を教える

検索する単語を検索する場合は、1つずつチェックしてください.

個のエラー単語が発生した場合、LPS配列の-1位置の値はすべてのエラー単語に接続されます.

LPSアレイの-1位置の値:1
LPSアレイにおける-1位置の値-1:0

LPSアレイの-1位置の値が0の場合、エラーの単語位置に直接接続されます.

LPSアレイの-1位置の値:0

総プロセス

完全なコード

# LPS 배열
def getLpsArray (target):
    lpsArray = [0]

    i = 1
    j = 0

    while(i < len(target)):
        
        if(target[i] == target[j]): # 같다면 j 를 한 칸 앞( -> )으로 보내줍니다.
            j += 1
            i += 1
            lpsArray.append(j)
        else: # 같지 않다면 현재 문자와 일치하는 문자가 나타나거나 j 가 0번째 칸으로 갈 때까지 이동합니다.
            if(j > 0):
                j -= 1
            elif(j == 0):
                lpsArray.append(0)
                i += 1

    return lpsArray



# KMP 알고리즘
def kmpSearch(text, target, lpsArray):
    i = 0
    j = 0
    isFind = False

    while i < len(text):
        if (text[i] == target[j]):
            i += 1
            j += 1
        else:
            if (j != 0):
                j = lpsArray[j-1]
            else:
                i += 1
        
        if ( j == len(target) ):
            isFind = True
            return i - j
            
    if(not isFind):
        return -1




def main():

    target = "aaabaaac"
    text = "aabaaabaaabaaac"

    lpsArray = getLpsArray(target)
    print(kmpSearch(text, target, lpsArray))


if __name__ == '__main__':
    main()

出力:7
コメントサイト
https://codinggladiators.com/index.php/2021/06/26/how-knuth-morris-pratt-string-searching-algorithm-works/
https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221240660061&referrerCode=0&searchKeyword=KMP