[고급 알고리즘] KMP 문자열 검색 알고리즘(KMP String Search Algorithm)

KMP 문자열 검색 알고리즘(KMP String Search Algorithm)

1. 개요

KMP 알고리즘은 문자열 검색 알고리즘 중 하나로, 주어진 텍스트 내에서 특정 패턴을 찾는 데 사용됩니다. 이 알고리즘은 1975년에 Donald Knuth, Vaughan Pratt, 그리고 James H. Morris에 의해 동시에 발견되었습니다. 그들의 이름의 이니셜을 따서 KMP 알고리즘이라고 불립니다.

기본적인 문자열 검색 알고리즘은 텍스트의 각 위치에서 패턴을 찾기 시작하므로, 최악의 경우 시간 복잡도가 O(NM)이 될 수 있습니다. 여기서 N은 텍스트의 길이이고, M은 패턴의 길이입니다. 반면 KMP 알고리즘은 텍스트를 한 번만 훑으면서 패턴을 찾을 수 있습니다.

2. 특징

1. 부분 일치 테이블(Partial Match Table): KMP 알고리즘의 핵심은 패턴 내에서의 부분 일치 정보를 미리 계산하고 저장하는 것입니다. 이 테이블은 패턴의 각 위치에서, 일치하지 않을 경우 다음으로 어디로 점프해야 하는지를 알려줍니다.
2. 점프(Jumping): 기본 문자열 검색 알고리즘은 일치하지 않는 경우 텍스트의 다음 위치로 이동하지만, KMP 알고리즘은 부분 일치 테이블을 사용하여 불필요한 비교를 건너뛰고 더 큰 간격으로 점프할 수 있습니다.
3. 효율성: KMP 알고리즘은 텍스트 내에서 패턴을 찾을 때 텍스트의 각 문자를 한 번만 검사합니다. 따라서 시간 복잡도는 O(N)입니다.

3. 예시

def KMPSearch(pat, txt):
    M = len(pat)
    N = len(txt)
    lps = [0]*M
    j = 0
    computeLPSArray(pat, M, lps)
    i = 0
    while i < N:
        if pat[j] == txt[i]:
            i += 1
            j += 1
        if j == M:
            print("Found pattern at index " + str(i-j))
            j = lps[j-1]
        elif i < N and pat[j] != txt[i]:
            if j != 0:
                j = lps[j-1]
            else:
                i += 1

4. 시간 복잡도

KMP 알고리즘의 시간 복잡도는 O(N)입니다. 여기서 N은 텍스트의 길이를 나타냅니다.