백준 1786 찾기 - C++/KMP

KMP 알고리즘의 입문 문제이다.

문제에 친절하게 KMP 알고리즘에 대한 설명이 있으니 천천히 읽어보면 좋을 것 같다.

 

KMP 알고리즘은 크게 두 가지 단계를 거친다.

 

1. 찾으려는 문자열(P)의 겹치는 접두사와 접미사를 찾아 그 위치를 기록하기.

2. 본 문자열(T)에서 찾으려는 문자열 찾기.

 

위 두 단계는 유사한 과정을 거치며, 접두사와 접미사가 중복되는 것을 이용하여

불필요한 탐색 횟수를 건너뛰려는 것이 궁극적인 목표이다.

 

KMP 알고리즘을 이용하면 for 문 한 번에 모두 검색이 가능하므로

찾으려는 문자열의 길이를 M으로 두면, 1번 단계에서 O(M)

본 문자열의 길이를 N 으로 두면, 2번 단계에서 O(N)의 시간복잡도가 요구된다.

 

1,2 의 공통적인 핵심 아이디어는, 중복을 건너뛴다는 것이다.

 

---

 1.

 가령 ABCDABC 라는 문자열이 있다면, 접두사만 따로 떼어서 보면 A, AB, ABC, ABCD, ABCDA, ABCDAB, ABCDABC 로 문자열의 길이만큼 개수가 나온다.

접두사로 따로 떼어서 보는 이유는 접두사와 접미사가 어디까지 중복되냐를 보기 위해서이며, 사실 따로 떼어서 볼 필요는 없다.

 

ABCDABC 는 접두사 ABC 와 접미사 ABC 가 같다.

이 때 현재 index 를 i, 접두사의 index를 j 로 두면 idx[i] = ++j; 가 된다. 

왜냐하면, j 는 겹치는 접두사의 다음 index 를 가리키도록 만들기 위해서이다.

 

이 때 j >= 0 을 항상 만족해야하고, 만약 P[i] != P[j] 라면 j = idx[j-1] 이 되어야 한다.

왜냐하면, 다르기 전까지(같았던 곳까지) index의 다음 것으로 간 후 비교하면 

같은 곳까지의 인덱스를 점프하듯이 단축시키면서 찾을 수 있기 때문이다.

 

---

2.

 그 다음은 for i = 0~N 까지 돌면서 같은 것을 찾는 과정이다.

이 때 j 는 내가 찾으려는 문자열의 index로 취급하여 몇 개나 같은지를 계속해서 추적할 것이다.

만약 P[j] != T[i] 라면 j 는 1번과 마찬가지로 같았던 곳의 다음 번 인덱스로 바꿔준다. j = idx[j-1];

만약 P[j] == T[i] 라면 j 는 하나 증가하여 다음 문자를 가리키며,

이 때 j == M  이라면 하나를 찾은 것이므로 ans 에 추가해주고 j 는 다시 마지막 접미사가 접두사와 같은 지점의 다음 인덱스로 이동한다. j=idx[j-1];

 

위 방식을 그대로 코드로 구현하면 다음과 같다.

 

#include <cstdio>
#include <string>
#include <iostream>

using namespace std;



int n, m;
string Origin, Find;
int FindIdx[1000001];
int matchIdx[1000001];
int ans;

int main() {
	getline(cin, Origin);
	getline(cin, Find);
	n = Origin.length();
	m = Find.length();
	//making Find idx;
	int j = 0;
	for (int i = 1; i < m; ++i) {
		while (j > 0 && Find[j] != Find[i]) {
			j = FindIdx[j - 1];
		}
		if (Find[j] == Find[i]) FindIdx[i] = ++j;
	}
	
	//Searching
	j = 0;
	for (int i = 0; i < n; ++i) {
		while (j > 0 && Find[j] != Origin[i]) {
			j = FindIdx[j - 1];
		}
		if (Origin[i] == Find[j]) {
			++j;
			if (j == m) {
				matchIdx[ans++] = i-m+2;
				j = FindIdx[j - 1];
			}
		}
	}
	printf("%d\n", ans);
	for (int i = 0; i < ans; ++i) printf("%d ", matchIdx[i]);

}