Knuth Morris Pratt

KMP

관련문제

용어

찾을 글자를 편의상 P(Pattern 약자) 라고 하고 찾을 텍스트 소스를 T(Text 약자) 라고 하자.

시간복잡도

T 의 글자 하나마다 P 가 맞는지 하나씩 비교하면 시간복잡도가 O(\(\vert \mathrm{T} \vert \vert \mathrm{P} \vert\)) 가 되서 매우 느리다. 하지만 대신 T 를 하나씩 보면서 알게된 정보를 이용하면 O(\(\vert \mathrm{T} \vert + \vert \mathrm{P} \vert\)) 로 검색을 끝낼 수 있다. 이는 시간복잡도 상 최적인데, 뭔 글자인지도 모르고 검색을 할 순 없기 때문이다.

발상

기본적으로 P 와 T 를 한글자씩 비교해야한다. 만약 임의의 수 n 만큼 비교가 성공했다고 해보자. \(n = \vert \mathrm{T} \vert\) 라면 찾기에 성공한 것이고. \(n < \vert \mathrm{T} \vert\) 라면 찾기에 실패한 것이다. 이때 실패했을 때 우리는 \(n-1\) 개까지는 성공했다는 걸 알고 있다. 이걸 이용한다.

상세 설명

case 1.

P = abcab , T = abcdef 라고 해보자.

• P[0] == T[0] == ‘a’ => 누적 1.

• P[1] == T[1] == ‘b’ => 누적 2.

• P[2] == T[2] == ‘c’ => 누적 3.

• P[3] != T[3] == ‘d’ => 누적 3 에서 틀림.

그럼 다음 스텝은 어떻게 해야할까?

여기서 우리는 직관적으로 T의 4번째 글자와 P 의 첫번째글자부터 다시 비교해야함 을 알 수 있다.

• P[0] != T[3] == ‘d’ => 누적 0

• P[0] != T[4] == ‘e’ => 누적 0

• …

즉 이 경우에는 누적 스택인 3만큼 P 의 비교 인덱스를 줄였음을 알 수 있다. ( 3 => 0 )

case 2.

P = abaa , T = ababaa 라고 해보자.

• P[0] == T[0] == ‘a’ => 누적 1. (“a” 겹침)

• P[1] == T[1] == ‘b’ => 누적 2. (“ab” 겹침)

• P[2] == T[2] == ‘a’ => 누적 3. (“aba” 겹침)

• P[3] != T[3] == ‘b’ => 누적 3 에서 틀림.

그럼 다음 스텝은 어떻게 해야할까?

여기서 우리는 직관적으로 P[1] 부터 다시 비교하면 될거라고 생각할 수 있다.

• P[1] == T[3] == ‘b’ => 누적 2. (“ab” 겹침)

• P[2] == T[4] == ‘a’ => 누적 3. (“aba” 겹침)

• …

이번에는 누적된 값만큼 뒤로 가진 않는다. 대신 “ab” 가 겹치는 것을 확인했기 때문에 “ab” 이후에 “aa” 가 오는지 다시 확인을 하게 된다.

case 3.

P = abaabaa , T = abaababaabaa 라고 해보자. 5번째까진 스킵하겠다.

• P[5] == T[5] == ‘a’ => 누적 6.

• P[6] != T[6] == ‘b’ => 누적 6 에서 틀림. (“abaaba” 가 겹쳤음)

• P[2] != T[6] == ‘b’ => 누적 3 에서 틀림. (“aba” 가 겹쳤음)

• P[1] == T[6] == ‘b’ => 누적 2. (“ab” 가 겹침)

이번엔 비교과정이 더 길어졌다.

누적된 부분이 “abaaba” 이고 다음 부분이 ‘a’ 가 아니라 ‘b’ 라서 비교에 실패한다.

그런데 “abaaba” 는 “aba/aba” 로 쪼갤 수 있다. 뒷부분의 “aba” 가 비교에 성공했으므로, 다시 P 의 처음부터 비교하지 않고, 앞부분의 “aba” 부터 비교를 시작해도 상관이 없다. 그럼 “aba” 다음에 “a” 가 오는지 확인하면 된다. 하지만 그렇지 않고 다시 비교를 해야한다.

“aba” 는 다시 __ “a/b/a”__ 로 나눌 수 있고, 마찬가지로 앞부분의 “a” 부터 비교를 하여 “a” 다음에 “b” 가 오는지 확인하면 된다. 그리고 비교는 성공하고, “ab” 만큼 누적된다.

이렇게 “abaaba” 부터 P 의 앞부분에 오는 문자와 겹치는지 여부를 재귀적으로 반복해서 P 를 비교할 위치를 찾으면 된다.

FailTB

위에서 설명했듯, P 와 비교하다 실패하면, 비교가 누적된 부분에서 앞부분과 뒷부분의 겹치는 부분이 있을 때, 앞부분 바로 다음부터 다시 비교 하면 된다. 이는 P 의 인덱스마다 앞부분의 몇번째 인덱스까지 겹치는지 미리 저장해두면 상수시간 내에 수행될 수 있다. 이를 저장한 배열을 failTB[] 라고 하자.

예를들면 failTB[4]==2 에서 P[4] 까지 비교가 성공하고 P[5] 에서 실패하면 P[failTB[5-1]] 즉 P[2] 랑 다시 비교 시작하게 된다.

다음은 이를 재귀적으로 구현한 코드이다.

int MakeFailTB(char Tc, const string& P, int j)
{
	if (Tc == P[j]) return j + 1;
	if (j == 0) return 0;
	return MakeFailTB(Tc, P, failTB[j-1]);
}

int main()
{
	...
	for(int i = 1, j = 0; i < P.size(); i++)
		j = failTB[i] = MakeFailTB(P[i], P, j);
}

• j 는 앞부분의 끝 , i 는 뒷부분의 끝 의 인덱스로 지금 비교하는 위치를 가리킨다. 앞부분, 뒷부분 으로 나뉘는건 길이가 2부터 가능하니까 i=1, j=0 로 시작한다.
• MakeFailTB() 는 최대 j 번 반복되는데, j 는 최대 P.size() 만큼 증가하므로 반복문 동안 합쳐서 최대 P.size() 번 계산된다. 그래서 시간복잡도가 O(\(2\vert \mathrm{P} \vert\)) 이다.

for (int i = 1, j = 0; i < P.size(); i++)
{
	while (j > 0 && P[i] != P[j]) j = failTB[j - 1];
	if (P[i] == P[j]) failTB[i] = ++j;
	// else failTB[i] = 0;
}

위 재귀식을 반복문을 바꾸면 위와 같다.

비교

vector<int> r;
for (int i = 0, j = 0; i < T.size(); i++)
{
	while (j > 0 && T[i] != P[j]) j = failTB[j - 1];
	if (T[i] == P[j]) {
		if (j == P.size() - 1) {
			r.push_back(i - j + 1);
			j = failTB[j];
		}
		else j++;
	}
}

failTB[] 구할 때와 똑같다. 앞부분과 뒷부분의 끝이 다르면 앞에서 구한 failTB[] 를 이용해 앞부분과 뒷부분이 겹치는 가장 긴부분을 찾아낸다. 문자를 다 찾았을 때는 j = failTB[j] 를 수행한다는 점에 주의하자.