[BOJ 1786]

문제 바로가기 : https://www.acmicpc.net/problem/1786
문제 설명은 위 링크에서 확인해주시길 바랍니다.

Solution

KMP Algorithm

❗ 문제 출처에 KMP 알고리즘에 대해 자세히 설명이 되어 있습니다.

KMP 알고리즘은 두 문자열이 있을 때 문자열이 일치하는지 내지는 일치하는 횟수를 빠르게 파악하기 위해 사용할 수 있다.
두 문자열의 길이가 n, m(n<=m)일 때, 제일 간단한 방법으로 일일이 비교하게 되면 시간 복잡도가 O(nm)이다.
하지만 KMP 알고리즘을 이용하면 O(n+m)에 답을 구할 수 있다! 문자열이 반복되는 경우 효과적이다.

review

문제 설명에서 ‘k를 j에 대한 함수로 구해놓으면 편하게 구할 수 있다’라고 해서 saveP[]를 선언하고 값을 저장했다.
saveP[]는 전역 변수로 설정했으므로 기본값은 모두 0이다. saveP[0]은 비교할 문자가 없으므로 무조건 0이 된다.
때문에 값을 저장해줄 필요가 없으므로 i=1부터 그리고 idxP>0 이라는 조건을 걸었다.

//make saveP
int idxP = 0;
for (int i = 1; i < P.size(); i++) {
		while (idxP>0 && P[i] != P[idxP])
			idxP = saveP[idxP-1];
		if (P[i] == P[idxP])
			saveP[i] = ++idxP;
}

여기서 while문에 대해서 더 설명하면, idxP를 계속 업데이트해주나 saveP[i]는 0으로 둔다.
업데이트된 idxP는 다음 인덱스에서 이용된다. 예를 들어보자.

idx :     0 1 2 3 4 5 6 7
P :       A B C D A B D A
saveP[] : 0 0 0 0 1 2 0 1

3번째까지는 반복되는 문자가 없으므로 saveP[0~3]=0 이다. 하지만 4번째에서 반복되는 문자가 등장하므로 saveP[4]=1 이다.
기본적으로 특정 인덱스에서 값을 업데이트할 때 컨셉은 해당 인덱스에서 값이 다르고 이전 문자열이 모두 같다는 점이다.
때문에 5번째에선 직전 값(idxP)을 이용한다. 2번째 문자와 같으므로 saveP[5]=2가 된다.
6번째에서는 P[2]와 일치하지 않으므로 idxP가 업데이트된다. 과정은 다음과 같다.

//처음 idxP = 2
//idxP = saveP[idxP-1]
idxP = saveP[1]; // B가 반복되는 곳에서 시작되도록 업데이트

//=> idxP = 0;
//1번째 앞에서 반복되는 B는 없으므로 idxP는 0이 된다.

알고리즘의 핵심 부분은 다음과 같이 진행된다.

//process
idxP = 0;
vector<int> ans;
for (int i = 0; i < T.size(); i++) {
	//불일치
	while (idxP > 0 && T[i] != P[idxP])
		idxP = saveP[idxP - 1];
	//일치
	if (T[i] == P[idxP]) {
		//모든 문자열 일치
		if (idxP == P.size() - 1) {
			ans.push_back(i - idxP + 1);
			idxP = saveP[idxP]; //마지막 위치가 반복되는 문자일 수 있음
		}
		//부분 문자열 일치
		else {
			idxP++;
		}
	}
}

불일치일 때 매커니즘은 위에서 설명한 부분과 같으므로 생략.
i는 문자열 T에서, idxP는 문자열 P에서 움직이도록 분리되어 있는게 포인트다!
i와 idxP는 한 문자를 탐색할 때마다 조건에 맞춰 독립적으로 꾸준히 움직인다. O(n+m)에 탐색이 끝나는 이유다.

idxP는 문자가 일치하면 1씩 계속 증가하고 마지막 인덱스에 도달하면 ans에 푸시된다.
시작포인트가 답이므로 i-idxP+1이 들어간다.
근데 P의 마지막 문자는 반복되는 문자열일 수도 있으므로 idxP를 0이 아닌 saveP[idxP]로 업데이트 해준다.
예시는 다음과 같다.

idx :     0 1 2 3 4 5 6
P :       A B C D A B C
saveP[] : 0 0 0 0 1 2 3

P[6] == P[2] 인데 i는 계속 한 칸씩 진행하므로 앞에 있는 A, B를 탐색하지 않는다.
때문에 idxP = 3으로 설정해주면 P[0~2]를 탐색할 필요없이 T[i+1] == P[3]으로 시작하게 된다.