4.4. Knuth Morris Pratt (KMP 알고리즘)

CS - 4. String Search and Manipulations - 4.4. Knuth morris pratt 

 

Knuth Morris Pratt

💡Knuth morris pratt is a string searching algorithm that uses a precomputed array to find the substring in a string. This array is known as the prefix function. The prefix function is the longest prefix that is also a suffix of a substring. The prefix function is used to skip the characters that are already matched. The algorithm is as follows:

• Compute the prefix function of the substring.
• Traverse through the string and substring simultaneously.
• If the characters match, increment the index of both the string and substring.
• If the characters don’t match, increment the index of the string by the value of the prefix function at the index of the substring.

 

KMP 알고리즘은 미리 계산된 배열을 사용하여 문자열의 하위 문자열을 찾는 문자열 검색 알고리즘입니다. 이 배열을 접두사 함수라고 합니다. 접두사 함수는 하위 문자열의 접미사이기도 한 가장 긴 접두사입니다. 접두사 함수는 이미 일치하는 문자를 건너뛰는 데 사용됩니다. 알고리즘은 다음과 같습니다:

 

• 하위 문자열의 접두사 함수를 계산합니다.
• 문자열과 부분 문자열을 동시에 순회합니다.
• 문자가 일치하면 문자열과 부분 문자열의 인덱스를 모두 증가시킵니다.
• 문자가 일치하지 않으면 문자열의 인덱스에서 부분 문자열의 인덱스에 있는 접두사 함수의 값만큼 문자열의 인덱스를 증가시킵니다.

Knuth-Morris-Pratt (KMP) 알고리즘은 문자열 검색 알고리즘으로, 주어진 텍스트에서 패턴이 일치하는 위치를 찾는데 사용됩니다. 기본적인 아이디어는 간단한 문자열 검색 알고리즘과 다르게, 패턴의 각 위치에서 불일치가 발생하면 패턴을 가능한 한 최대한 이동시키는 것입니다. 이를 위해 "부분 일치" 테이블(또는 "실패 함수")을 미리 계산합니다.

 

이는 워드프로세서같은 수천, 수백만 단어에서 특정 문자열 패턴을 찾을때 효율적으로 수행할 수 있습니다. KMP 알고리즘이 텍스트 내에서 가장 빠르게 원하는 문자열을 찾아내는 알고리즘 이기 때문입니다.

 

In Python

def kmp_search(text, pattern):
    pattern_length = len(pattern)  
    text_length = len(text)  
    lps = [0]*pattern_length  # 부분 일치 테이블 초기화
    j = 0  # 패턴 문자열의 인덱스

    # 부분 일치 테이블 계산(아래 함수에 정의함)
    compute_lps_array(pattern, pattern_length, lps)

    i = 0  # 텍스트 문자열의 인덱스
    while i < text_length:
        if pattern[j] == text[i]:  # 문자가 일치하면 둘 다 증가
            i += 1
            j += 1

        if j == pattern_length:  # 패턴 문자열을 끝까지 비교했으면 패턴 발견
            print("패턴이 발견된 위치: " + str(i-j))
            j = lps[j-1]  # 다음 비교를 위해 인덱스 감소

        # 패턴이 불일치하고 텍스트가 아직 끝나지 않았다면
        elif i < text_length and pattern[j] != text[i]:
            if j != 0:  # 패턴의 중간에서 불일치가 발생하면
                j = lps[j-1]  # lps값을 이용하여 j를 감소
            else:  # 패턴의 첫 번째 문자에서 불일치가 발생하면
                i += 1  # 텍스트 문자열의 인덱스만 증가


# 부분 일치 테이블(LPS 배열) 계산 함수
def compute_lps_array(pattern, pattern_length, lps):
    length = 0  # 이전에 계산된 가장 긴 접두사/접미사의 길이
    lps[0] = 0  # lps[0]은 항상 0
    i = 1  # lps 인덱스

    # 패턴의 두 번째 문자부터 lps 배열을 채워나감
    while i < pattern_length:
        if pattern[i] == pattern[length]:  # 패턴의 문자가 일치하면
            length += 1  # 길이 증가
            lps[i] = length  # lps 배열에 길이 값 할당
            i += 1
        else:
            if length != 0:  # 이전 인덱스에서 일치가 발생했으면
                length = lps[length-1]  # 이전 lps 값을 사용
            else:  # 이전 인덱스에서 일치가 없었으면
                lps[i] = 0  # lps 값은 0
                i += 1

 

 

 

 

 

방금 위에 쓴 글을 가지고 KMP 알고리즘을 적용해보겠습니다.

 

 

 

활용

 

https://www.acmicpc.net/problem/1786(백준 1786 찾기)

실제로 ctrl + F 를 통해서 찾기를 하는 방법을 구현하는 문제.