[Algorithm] 문자열 검색 - KMP 알고리즘

* Python을 기준으로 합니다

---

문자열 검색 - KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)

- 개념

• KMP (Knuth-Morris-Pratt) 알고리즘 : 불일치가 감지되기 이전까지의 문자열은 다시 비교할 필요가 없다는 점을 활용함
  • 이를 통해 $O(NM)$의 time complexity를 가지는 Naive approach에 비해 KMP 알고리즘은 $O(N+M)$의 time complexity로 줄일 수 있음
  • KMP를 위한 문자열 전처리 : 불일치가 발생했을 때 건너뛸 문자 수를 결정하기 위함
    1. 먼저 건너뛸 문자 수를 결정하기 위해, 패턴 크기 `M`과 동일한 크기의 배열 `lps[]`를 선언함
       - `lps[]`는 길이가 최대인 접두사(prefix)-접미사(suffix) 배열을 의미
    2. 이후 sub-string에 대해 `lps[i]`에 `pattern[0:i]`의 접두사-접미사에 해당하는 가장 긴 패턴 길이를 저장함
    3. lps[]의 값 계산을 위해, 가장 긴 접두사-접미사 값을 `l`에 할당
       - `pattern[l]`과 `pattern[i]`가 일치하면 `l`을 증가시키고 증가된 값을 `lps[i]`에 할당
       - 서로 일치하지 않고 `l`이 0이 아니면 `l`을 `lps[len-1]`로 업데이트
  • KMP의 동작
    1. `lps[]` 배열을 계산한 다음,
    2. `pattern[j]`와 `text[i]`가 일치하는 동안 반복해서 `i`와 `j`를 증가시킴
    3. 이때 `j`가 패턴 크기 `M`과 같으면 결과값을 배열에 저장
    4. 같지 않으면
       - `j`가 0이면 `i`를 증가시키고
       - `j`가 0이 아닌 경우, `lps[j-1]`로 이동

KMP 알고리즘의 동작

- 구현

1. KMP 알고리즘의 구현

• 불일치가 나타나는 경우, `lps` 배열을 사용하여 탐색 범위를 줄임

def KMP_table(pattern):
    M = len(pattern)

    lps = [0]*M #접두사-접미사 배열 lps를 pattern 길이만큼 선언
    l = 0  # 가장 긴 접두사-접미사 길이를 저장하는 용도
    i = 1

    while i < M:
        if pattern[i] == pattern[l]: #일치하면
            l += 1 #l을 증가시키고
            lps[i] = l #해당 값을 lps[i]에 할당
            i += 1
        else: #일치하지 않고
            if l != 0: #len이 0이 아니면
                l = lps[l-1] #l을 lps[l-1]로 업데이트
            else: #len이 0이면
                lps[i] = 0 #초기화
                i += 1
    
    return lps

def KMP(pattern, text):
    M = len(pattern)
    N = len(text)

    j = 0  #pattern index
    i = 0  #text index
    result = []

    # lps 계산
    lps = KMP_table(pattern)

    while (N - i) >= (M - j):
        if pattern[j] == text[i]: #문자열과 패턴이 일치하면
            # 다음 index로 이동
            i += 1
            j += 1

        if j == M: #패턴 index가 패턴 크기와 일치하면
            result.append(i-j) #결과값 저장
            j = lps[j-1] #패턴 index 이동

        elif i < N and pattern[j] != text[i]: #일치하지 않으면
            if j != 0: #패턴 index가 0이 아니면
                j = lps[j-1] #패턴 index 이동
            else: #패턴 index가 0이면
                i += 1 #문자열 index 이동

    return result