(BOJ) 찾기_1786번

문제

https://www.acmicpc.net/problem/1786

1. 문자열 T에 문자열 P가 몇 번 나오는지 출력
2. 문자열 P가 문자열 T의 몇 번째 인덱스에 나오는지 나열

간단하게 말해서 이 두 가지를 구하는 문제이다.

접근

이 문제를 브루트 포스하게 풀게 되면, 문자열 T의 길이를 m, 문자열 P의 길이를 n이라고 했을 때, O((m-n+1)*n) 만큼의 시간이 걸리게 된다. 이렇게 되면 탐색했던 부분을 되짚어서 다시 탐색하는 작업을 반복하게 될 것이고 매우 비효율적이다.

문제를 읽어보면, 딱 KMP 알고리즘에 대한 설명인데, 이제 KMP 알고리즘에 대해 알아볼 예정이다.

KMP 알고리즘

KMP 알고리즘이란, Knuth-Morris-Pratt 알고리즘의 줄임말로, 오토마타를 이용한 매칭과 동기가 유사하지만, 준비 작업이 더 단순하다.

제시된 문제의 예제로 살펴보자면, 현재 T는 ABC ABCDAB ABCDABCDABDE이고, P는 ABCDABD이다. 두 문자열을 비교하기 전에 P에 대한 사전 작업이 필요하다. 그 사전 작업이 실패함수를 정의하는 것이다.

실패함수란?
'문자 매칭에 실패했을 때, 얼만큼 건너뛰어야 하는가?'를 알기 위해 사용한다.

실패함수를 만들 때의 핵심은, 문자열의 앞부분부터 부분 문자열을 따졌을 때 본인과 같은 부분 문자열 제외 접두사와 접미사가 같은 최대 길이의 부분 문자열을 찾는 것이다.

문자열 P를 예로 들자면,

A
AB
ABC
ABCD
ABCDA
ABCDAB
ABCDABD

여기서 빨간색으로 표시한 부분이 이에 해당한다. 이를 하나의 배열로 저장해놓는 작업이 필요하다.

i = 0, j = 0

인덱스	0	1	2	3	4	5	6
값	0	0	0	0	0	0	0

먼저, 문자열 길이만큼의 배열을 생성한 후, 0으로 초기화해두고, 각 인덱스를 표시할 변수 i와 인덱스에 대한 값이 될 변수인 j를 선언하고 0으로 초기화한다. 이제 앞에서부터 각 부분 문자열에 대해 따져봐야 하는데 이때!

인덱스 0이 아니라 1부터 따져봐야 한다!!! 본인 문자열과 같은 부분 문자열은 제외해야하기 때문이다. 전체 문자열 "A"와 부분 문자열 "A"는 같으므로 무조건 접두사와 접미사가 같은 최대 길이의 부분 문자열의 길이는 0이 될 수밖에 없다.

1. A

i = 0, j = 0

인덱스	0	1	2	3	4	5	6
값	0	0	0	0	0	0	0

2. AB

i = 1, j = 0

인덱스	0	1	2	3	4	5	6
값	0	0	0	0	0	0	0

A	B
	A	B

AB에서 본인 제외 접두사와 접미사가 같은 부분 문자열이 없으므로 j는 0이 된다.

3. ABC

i = 2, j = 0

인덱스	0	1	2	3	4	5	6
값	0	0	0	0	0	0	0

A	B	C
		A	B	C

ABC에서 본인 제외 접두사와 접미사가 같은 부분 문자열이 없으므로 j는 0이 된다.

차례대로 탐색한다고 생각하면

A	B	C
	A	B	C

여기서부터 비교를 시작해야 한다고 생각할 수도 있겠지만, 이 과정은 필요가 없다. 이미 위에서 현재 빨간색으로 표시된 부분은 같은 문자가 아니라는 사실을 알아냈기 때문에 다시 탐색할 필요가 없어진다.

4. ABCD

i = 3, j = 0

인덱스	0	1	2	3	4	5	6
값	0	0	0	0	0	0	0

A	B	C	D
			A	B	C	D

ABCD에서 본인 제외 접두사와 접미사가 같은 부분 문자열이 없으므로 j는 0이 된다.

여기서도 마찬가지로 차례대로 탐색한다고 생각하면

A	B	C	D
	A	B	C	D

A	B	C	D
		A	B	C	D

이 두 과정이 필요 없어지게 된다. 첫 번째의 경우 2.의 과정에서 알게 되었으며 두 번째의 경우 3.의 과정에서 알게 되었기 때문이다.

5. ABCDA

i = 4, j = 1

인덱스	0	1	2	3	4	5	6
값	0	0	0	0	1	0	0

A	B	C	D	A
				A	B	C	D	A

ABCDA에서 본인 제외 접두사와 접미사가 같은 부분 문자열은 "A"가 된다. 따라서 j를 1만큼 증가시키고 인덱스 4의 위치에 값을 저장한다.

여기서 j = 1은 현재 인덱스까지의 부분 문자열에서 본인 제외 접두사와 접미사가 같은 부분 문자열의 최대 길이는 1이라는 것을 나타낸다.

6. ABCDAB

i = 5, j = 2

인덱스	0	1	2	3	4	5	6
값	0	0	0	0	1	2	0

A	B	C	D	A	B
				A	B	C	D	A	B

ABCDAB에서 본인 제외 접두사와 접미사가 같은 부분 문자열은 "AB"가 된다. 따라서 j를 1만큼 증가시키고 인덱스 4의 위치에 값을 저장한다.

7. ABCDABD

i = 6, j = 0

인덱스	0	1	2	3	4	5	6
값	0	0	0	0	1	2	0

A	B	C	D	A	B	D
				A	B	C	D	A	B	D

ABCDABD에서 본인 제외 접두사와 접미사가 같은 부분 문자열이 없는 상태이다. 따라서 j가 0이 된다.

A	B	C	D	A	B	D
				A	B	C	D	A	B	D

현재 상태는 다음과 같은데,

A	B	C	D	A	B	D
					A	B	C	D	A	B	D

이렇게 한 칸만 밀어서 옮길 필요는 없다. 이미 본인 "A" 앞의 "AB"라는 부분문자열이 본인의 접두사와 같다는 것을 알고있기 때문이다. 따라서 본인을 포함한 접미사와 같은 최대 길이의 접두사가 있는지만 알아보면 된다.

1. j를 갱신하기 전(j = 2)인 상태에서 인덱스상 j번째 문자랑 현재 비교 대상 문자를 비교해본다. (흰색 칸의 문자열의 인덱스상 6번째 문자 'A' vs 회색 칸의 문자열의 인덱스 상 2번째 문자 'C')
2. 두 문자가 다르므로 비교 대상은 인덱스상 j-1번째 저장된 배열의 값의 문자열이 된다. 즉, 실패함수에 저장된 배열에서 첫 번째 인덱스의 값은 0이므로 인덱스상 0번째 문자인 'A'가 비교 대상이 된다. 'A'와 'D'는 다르고 접두사와 접미사가 같은 부분 문자열은 없게 된다.

실패함수는 다음과 같다.

인덱스	0	1	2	3	4	5	6
값	0	0	0	0	1	2	0

이제 이 실패함수를 가지고 문자열을 비교하는 시간을 갖게 된다. 흰색 칸에 있는 문자열을 배열 1, 회색 칸에 있는 문자열을 배열 2라고 생각할 예정이다. 또한, 배열 1 내에서 가리키는 인덱스를 i, 배열 2 내에서 가리키는 인덱스를 j라고 둘 예정이다.

A

B

C

-

A

B

C

D

A

B

-

A

B

C

D

A

B

C

D

A

B

D

E

A

B

C

D

A

B

D

먼저 이 상태에서 시작한다. 배열 1과 배열 2를 비교했을 때 i와 j가 0, 1, 2인 경우 각각 'A', 'B', 'C'로 같은 것을 볼 수 있다.

A

B

C

-

A

B

C

D

A

B

-

A

B

C

D

A

B

C

D

A

B

D

E

A

B

C

D

A

B

D

i와 j가 3일 때, ' '와 'D'로 문자가 다른 상황인데, 여기서 실패함수를 사용하게 된다.



실패함수

인덱스	0	1	2	3	4	5	6
값	0	0	0	0	1	2	0

j - 1은 2가 되고, 실패함수[2]가 갖고있는 값은 0이 된다. 따라서 j=0이 되고 배열2[0] = 'A'가 되며 이는 비교 대상이 된다. 즉,

A

B

C

-

A

B

C

D

A

B

-

A

B

C

D

A

B

C

D

A

B

D

E

A

B

C

D

A

B

D

다음과 같은 상황이 된다. j=0임에도 불구하고 ' '과 일치하지 않으므로 이 때는 한 칸 밀어낸다.



i = 4, j =0

A

B

C

-

A

B

C

D

A

B

-

A

B

C

D

A

B

C

D

A

B

D

E

A

B

C

D

A

B

D

해당 인덱스부터 같은 문자에 대해서는 쭉 진행했을 때 "ABCDAB"까지 같은 것을 확인할 수 있다. 순차적으로 i와 j를 갱신했을 때, i = 10, j = 6이 된다.

i = 10, j = 6

A

B

C

-

A

B

C

D

A

B

-

A

B

C

D

A

B

C

D

A

B

D

E

A

B

C

D

A

B

D

배열 1의 i번째 문자 ' '와 배열 2의 j번째 문자 'D'가 다르다. 이제 또 실패함수를 사용해야 한다.

실패함수

인덱스	0	1	2	3	4	5	6
값	0	0	0	0	1	2	0

j - 1는 5가 되고 실패함수[5]=2가 되므로 배열2[2]의 문자인 'C'와 비교해야 한다.

그런데 잠시... 왜 이렇게 하는 것일까?

본인은 실패함수 내의 값을 해당 인덱스까지의 부분문자열의 접두사와 접미사의 최대 길이라고도 생각하는 동시에, 비교해야할 문자의 지표라고도 생각한다.

일단 현재 단계에서 실패함수에 따라 비교할 문자열을 이동시켜보면,

A

B

C

-

A

B

C

D

A

B

-

A

B

C

D

A

B

C

D

A

B

D

E

A

B

C

D

A

B

D

이 상태가 되는데,

실패함수 왈 : j = 5가 갖고있는 값 2는 배열 2에서 인덱스상 1번째까지의 부분 문자열은 같으니, 배열 2의 인덱스상 두 번째의 문자열이랑 비교하라.

라는 뜻과 같다. 따라서 배열1[10]의 문자인 ' '이랑 배열2[2]의 문자인 'C'를 비교하면 된다.
그런데, 또 같지 않으므로 실패함수를 다시 본다.



실패함수

인덱스	0	1	2	3	4	5	6
값	0	0	0	0	1	2	0

j - 1 = 1이고 실패함수[1] = 0이므로, 아까와 같은 원리로 문자열의 위치를 옮기면 다음과 같다.

A

B

C

-

A

B

C

D

A

B

-

A

B

C

D

A

B

C

D

A

B

D

E

A

B

C

D

A

B

D

배열1[10]과 배열2[0]을 비교하게 된 것이다.

.
.
.

이와 같은 원리로 계속 비교해나가면 된다.

코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int* getPi(string P);
void KMP(string T, string P, int* pi);
int main() {
	string T;
	string P;
	getline(cin, T);
	getline(cin, P);

	int* pi = getPi(P);

	for (int i = 0; i < P.size(); i++) {
		cout << pi[i] << " ";
	}
	KMP(T, P, pi);

	if (pi != NULL) {
		delete[]pi;
		pi = NULL;
	}
	
	return 0;
}

int* getPi(string P) {
	int* pi = new int[P.size()]{ 0, };
	int j = 0;
	pi[0] = 0;

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

		if (P[i] == P[j]) {
			pi[i] = ++j;
		}
	}
	return pi;
}

void KMP(string T, string P, int* pi) {
	vector<int> v;
 	int j = 0;
	int count = 0;
	for (int i = 0; i < T.size(); i++) {
		while ((T[i] != P[j] && j > 0)){
			j = pi[j - 1]; 
		}

		if (T[i] == P[j]) {
			j++;
			if (j == P.size()) {
				v.push_back(i - P.size() + 2); 
				count++;
			}
		}
	}

	cout << count << endl;
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
}