KMP 문자열 검색

▼ 다들 엄청 자세하게 설명해주셨다 ! ㅜㅜ

KMP : 문자열 검색 알고리즘

[Python] KMP 알고리즘으로 문자열 찾기

[Python]KMP 알고리즘

 

1. KMP (Knuth, Morris, Pratt)란?

🖐 찾고자하는 문자열을 찾아내는 알고리즘!

 

2. 생각해보기

👉 ABBDCFDNABAVVBSAAB 에서 'AB'는 몇번?

       AB  -> 같다!

         AB  -> 다르다!

이렇게 순서대로 대입해보면서 찾으면?  텍스트 길이 N, 패턴길이 M 으로 시간복잡도는 O(NM)

👉 접두사와 접미사를 사용하자!

👉 Pi 배열을 사용하자! (LPS)

    (Pi[i]는 0~i까지 부분문자열 중 접두사 = 접미사가 될 수 있는 부분문자열 중 가장 긴 것의 길이)

👉 kmp알고리즘은 조금이라도 일치했었다는 정보를 활용해서 빠르게 구현가능!

 

3. 알고리즘 구현

def KMP(word, pattern):
    lps = get_pi(pattern)  # 파이 배열 가져오기
    
    result = []
    p_idx = 0
    
    for idx in range(len(word)):
        while p_idx > 0 and word[idx] != pattern[p_idx]:
            p_idx = lps[p_idx-1]
        if word[idx] == pattern[p_idx]:
            if p_idx == len(pattern)-1:
                result.append(idx - len(pattern)+2)
                p_idx = lps[p_idx]
            else:
                p_idx += 1
    return result
    
def get_pi(pattern): #Pi배열, LPS
    length = len(pattern)  # 패턴의 길이
    lps = [0] * length  # Pi 배열을 저장할 공간
    
    p_idx = 0  # 패턴의 인덱스
    for idx in range(1, length):  #파이 배열의 첫 값은 0임
        #p_idx가 0이 되거나, idx와 p_idx의 접근 값이 같아질 때 까지
        while p_idx > 0 and pattern[idx] != pattern[p_idx]:
            #p_idx가 0보다 크고 idx와 p_idx의 접근 값이 다를 때
            p_idx = lps[p_idx-1]  # 줄여서 계속 탐색
        
        if pattern[idx] == pattern[p_idx]:
            p_idx += 1  # 값이 일치하면 그 값을 저장
            lps[idx] = p_idx
    return lps

- 패턴 하나만 찾기

def kmp(target, pattern):
    N = len(target)  # 대상 문자열의 길이
    M = len(pattern)  # 패턴의 길이

    lps = [0] * (N + 1)
    lps[0] = -1  # 매칭이 실패했을 때 패턴의 어느 인덱스로 돌아가야하는지 계산

    j = 0  # 일치한 개수 저장
    for i in range(1, M):  # 0은 채웠으니 M(패턴의 길이까지)
        # 어느 위치로 돌아가야하는지 계산 : 앞쪽에 얼마나 많은 패턴이 맞았느냐
        lps[i] = j  # 앞서서 패턴이 일치했으면 j 증가
        if pattern[i] == pattern[j]:
            j += 1
        else:
            j = 0
    lps[M] = j
    # ==============================사전작업, LPS(Pi배열)=================
    i = 0  # 비교 텍스트 위치
    j = 0  # 패턴 시작 위치
    while i < N:
        if j == -1 or target[i] == pattern[j]:
            i += 1
            j += 1
        else:  # 틀렸음 => shift 찾기
            j = lps[j]
        if j == M:  # 패턴 찾음!
            return True
    return False

target ='abcdefg'
pattern = 'cde'
print(kmp(target, pattern))
# 출력 결과: True

 

4. 복잡도

👉 O(M+N)

 

---

어려워 ㅜㅜ