직선적 스트링 탐색 알고리즘

i = j = 0
while i < len(text) and j < len(pattern):
	if (text[i] == pattern[j]):
		j += 1
	else: j = 0
	i += 1
if j == len(pattern):
	# Match
else:
	# Not match

직선적 스트링 탐색 알고리즘은 텍스트를 순회하며 패턴과 일치하는지 확인하고,

일치하면 j를 증가시키며 패턴을 끝까지 순회하면 탐색에 성공한 것으로 본다.

일치하지 않으면 j를 0으로 만들어 패턴에 대한 순회를 처음부터 진행하게 한다.

문제점

일치하지 않은 경우 패턴에 대해 처음부터 다시 탐색하게 되는데, 이런 구조를 가져갈 경우 패턴과 의 비교 중에 불일치가 발생하면 일치하는 부분에 대한 정보를 버리고, 처음부터 다시 비교를(j ← 0) 하게 된다. 아래와 같이 패턴이 짧은 경우는 큰 문제가 안되지만, 패턴이 길어지게 되면 꽤나 비효율적이게 된다.

직선적 알고리즘 동작과정

아는건 두고, 모르는 부분만 검사할래!

불일치가 발생하면 일치하는걸 아는 부분은 그대로 두고, 그 뒤에부터 체크하면 이 문제가 해결된다. 이러한 문제 해결 과정을 이용하는 알고리즘이 “KMP 알고리즘” 이다.

next 배열 만들기

next 배열은 불일치가 발생했을 때 얼마나 앞으로 이동해야 하느냐 를 담고 있는 배열이다. “일치하는 것을 아는” 부분은 결국 “동일한 문자가 앞에 얼마나 있는가”에 대한 지표이다.

아래는 initNext 함수를 이용해 next 배열을 구하는 과정이다.

initNext 함수는 위/아래에 같은 패턴을 두고 이 둘을 비교하는 방식으로 작동하는데, 동작 과정은 다음과 같다.

1. 불일치하면 아래 패턴을 오른쪽으로 이동

2. 일치하면 패턴은 그대로 두고 아래 패턴에서 비교하는 커서를 이동

   이 때 커서 왼쪽에 있는 일치하는 문자열의 갯수를 next[j]에 삽입

유한 상태 장치

next 배열을 이용해 linkedlist 처럼 그려 놓은 구조도이다. 불일치가 발생하면 해당 위치에서 어디로 이동해야 하는지를 나타낸 것이다.

그런데 이 유한 상태 장치를 잘 살펴보면, 같은 문자의 위치로 이동하는 경우 다시 한번 비교를 해야 하므로 비효율적이다. 이 점을 개선해 이동한 자리의 next 노드로 이동해 더 나은 유한 상태 장치와 next 배열을 만들 수 있다.

아이디어

개선된 유한 상태 장치

next 배열을 이용해 탐색하기

curr_pos를 기준으로 initNext[curr_pos] 만큼 왼쪽으로 이동시킨다. 양수는 왼쪽, 음수는 오른쪽으로 이동시킨다.