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

KMP (Knuth-Morris-Pratt)  Algorithm

KMP 알고리즘은 주어진 문자열(M)에서 찾고자 하는 문자열(N)을 빠르게 찾아내는 알고리즘이다.

KMP 알고리즘은 O(N+M)으로 문자열을 전체비교하는 문자열 완전검탐색 (Brute Force, 시간복잡도 : O(NM))보다 더욱 빠르게 원하는 문자열을 검색할 수 있다.

 

KMP 알고리즘 이해

KMP 알고리즘의 이해는 다음 글들을 참고하면 좋을 것 같다.

KMP : 문자열 검색 알고리즘

[알고리즘/ 파이썬] KMP 알고리즘 알아보기

KMP 알고리즘 구현

KMP 알고리즘은 Python으로 다음과 같이 구현할 수 있다.

def get_pi(pattern : str) -> list:
	tb = [0 for _ in range(len(pattern))]
	i = 0
	for j in range(1, len(pattern)):
		while i > 0 and pattern[i] != pattern[j]:
			i = tb[i-1]
		if pattern[i] == pattern[j]:
			i += 1
			tb[j] = i
	return tb

def kmp(target : str, pattern : str) -> list:
	tb = get_pi(pattern)
	# kmp
	result = []
	i = 0
	for j in range(len(target)):
		while i > 0 and pattern[i] != target[j]:
			i = tb[i-1]
		if pattern[i] == target[j]:
			i += 1
			if i == len(pattern):
				result.append(j - i + 1)
				j = tb[i-1]
	retern result

하지만 내가 업무에 사용할 내용은 일치하는 문자열을 모두 찾는 것이 아닌 일치하는 문자열이 있는가를 찾는 알고리즘이였다.

따라서 다음과 같이 kmp 함수를 변경하였다.

def kmp(target : str, pattern : str) -> bool:
	tb = get_pi(pattern)
	# kmp
	i = 0
	for j in range(len(target)):
		while i > 0 and pattern[i] != target[j]:
			i = tb[i-1]
		if pattern[i] == target[j]:
			i += 1
			if i == len(pattern):
				return True
	return False