KMPアルゴリズム

一般的な検索アルゴリズムの例

通常,2つの文字列の共通部分を参照する際に用いられる方法はBrute Forceアルゴリズムである.このように探索を続けると,ソース文字列の長さがN,探索文字列の長さがMのとき,時間的複雑度はO(NM)となる.しかし,この方式は遅すぎて,KMPアルゴリズムによりこの時間的複雑さを低減する必要がある.

KMPアルゴリズムの時間複雑度

KMPアルゴリズムの時間的複雑度はO(n＋m)であり,これまで考えられていたO(NM)よりもはるかに速い.

KMPアルゴリズムの原理

接頭辞と接尾辞は、文字列の一番前と一番後ろに同じ文字列が現れる場合を指します.
これを基本概念としてKMPアルゴリズムを見ると

アルゴリズムは、以下の原理に従って動作する.
文字列をスキップしてブラウズした後、スキップした部分は同じでなければなりません.
しばらくスキップしたが、ソース文字列がナビゲーション文字列と一致しない場合は意味がありません.そのため、ナビゲーション文字列の前の部分がソース文字列の後の部分と同じになるまで、文字列ナビゲーションをスキップできます.

KMPアルゴリズムの核心は、検索文字列の前部分とソース文字列の後部分が文字列検索をスキップできることである。

KMPアルゴリズムの実装

白駿7575号ウイルス問題

まず前処理テーブルが必要です.

piは、接頭辞と接尾辞の最大長を格納する配列である.
これをコードとして実装すると、

前処理テーブル

def makeTable(tmp): # tmp는 패턴
    table = [0] * k # 패턴의 길이와 같은 크기의 테이블을 생성
    i = 0 # i를 이용해서 테이블을 갱신해 나간다.
    for j in range(1,k):
        while i > 0 and tmp[i]!=tmp[j]: # i랑 j랑 다르면 i는 table[i-1]로 돌아간다. 돌아가서 다시 j와 비교한다. 최대 공통 부분들이 Table에 들어 있기 때문에 계속 갱신해 주다가 0이 되면 0을 저장하고 다음 j로 넘어가는 식으로 동작한다.
            i = table[i-1]
        if tmp[i] == tmp[j]: # 만약 같으면 i값에 1을 더하고 table에 넣는다. 
            i += 1
            table[j] = i # i,j 둘다 하나씩 증가시킨다.
    return table

KMP関数の実装

def kmp(s,f,tmp):
    i = 0 # i를 통해 table 값을 갱신시킨다.
    for j in range(len(s)): 
        while i > 0 and s[j] != f[i]: # i와 j를 비교해서 다르면
            i = tmp[i-1] # 다르게 나온 곳-1번째 table 인덱스로 다시 되돌아가서 다시 비교한다.
        if s[j] == f[i]: # 모든 문자열이 전부 일치하면
            if i == k-1: # i가 패턴의 길이보다 하나 작으면 
                return 1 # 패턴을 찾은 것이므로 1을 반환
            else:
                i += 1 # 모든 문자열이 전부 일치하지 않으면 i를 하나씩 늘려서 비교한다.
    return 0 # 패턴을 못찾은 경우 0을 반환

ウイルスを識別する関数

for i in range(len(m[0])-k+1): # 코드의 길이는 접두사부분까지만 돌리면 되므로 0 부터 패턴의 길이만큼 뺀것+1을 돌리면 된다. 
    t = makeTable(m[0][i:i+k]) # k개의 길이만큼 코드가 같아야 하므로 그것을 패턴으로 makeTable 한다.
    for j in range(1,n): # 프로그램의 개수가 3개 이므로
        c = kmp(m[j],m[0][i:i+k],t) # kmp를 통해 비교해서 k개 이상 겹치는 코드가 존재하는지 판단
        if not c: # 코드가 존재하지 않으면
            c = kmp(m[j][::-1],m[0][i:i+k],t) # 뒤집어서도 비교해본다.
        if not c: # 만약 그래도 존재하지 않으면
            break # 반복문을 탈출하여 No 출력
        if j==n-1: # 만약 바이러스임을 감지하면 Yes 출력
            print('YES')
            exit(0) # 그대로 프로그램 종료
print('NO')

出典:https://injae-kim.github.io/dev/2020/07/23/all-about-kmp-algorithm.html、https://cantcoding.tistory.com/13?category=873347,https://cantcoding.tistory.com/35