KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)

KMP 알고리즘이란? 

KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 검색을 빠르게 수행하는 알고리즘입니다. 일반적인 문자열 검색(브루트포스)보다 더 효율적으로 검색할 수 있도록 설계되었습니다.

 

왜 KMP 알고리즘을 사용할까? 🙄

일반적인 문자열 검색은 O(N*M)의 시간이 걸리지만,

KMP는 O(N+M) 의 시간 복잡도를 가지므로 훨씬 빠르게 검색 가능합니다.

 

ex) 긴 텍스트에서 특정 패턴(문장)을 찾을 때 KMP를 사용하면 성능이 향상됩니다.

 

KMP 알고리즘의 작동 원리

KMP의 핵심은 LPS(Longest Prefix Suffix) 배열을 이용하는 것입니다!!

👻 즉, 반복되는 패턴을 미리 계산하여 불필요한 비교를 줄이는 방식! 

1. 패턴의 실패 함수 계산
2. 패턴 검색

실패 함수 계산

실패 함수는 패턴의 각 위치에서 가능한 가장 긴 접두사와 접미사의 길이를 기록한 배열

이 배열을 이용하여, 패턴의 일치가 중단되었을 때, 패턴의 앞부분을 다시 비교하지 않고 효율적으로 다음 비교를 시작할 수 있다. 

패턴 검색

텍스트에서 패턴을 검색할 때, 패턴의 각 문자와 텍스트의 현재 문자를 비교함

만약 불일치가 발생하면, 실패 함수를 사용하여 패턴의 다음 비교 위치를 결정함 

 

# KMP법으로 문자열 검색

def kmp_match(txt: str, pat: str) -> int :
	pt = 1 # txt를 따라가는 커서
    pp = 0 # pat를 따라가는 커서 
    skip = [0] * (len(pat) + 1) # 건너뛰기 표
    
    # 건너뛰기 표 만들기
    skip[pt] = 0 
    while pt != len(pat):
    	if pat[pt] == pat[pp]:
        	pt += 1
            pp += 1
            skip[pt] = pp
        elif pp == 0:
        	pt += 1
            skip[pt] = pp
        else:
        	pp = skip[pp]
            
    # 문자열 검색하기
    pt = pp = 0
    while pt != len(txt) and pp != len(pat):
    	if txt[pt] == pat[pp]:
        	pt += 1
            pp += 1
        elif pp == 0:
        	pt += 1
        else:
        	pp = skip[pp]
            
    return pt - pp if pp == len(pat) else -1
    
if __name__ == '__main__':
	s1 = input() # 텍스트용 문자열
    s2 = input() # 패턴용 문자열
    
    idx = kmp_match(s1,s2)
    
    if idx == -1:
    	print('텍스트에 패턴이 존재하지 않습니다.')
    else:
    	print(f'{(idx+1)}번째 문자가 일치합니다.')

 

 

KMP 알고리즘은 단순한 문자열 검색보다 훨씬 효율적인 알고리즘입니다.

📌 패턴이 겹치는 부분을 활용하여, 불필요한 비교를 줄이는 것이 핵심!
📌 시간복잡도는 O(N + M)으로 빠름!