[백준 1786] 찾기

문제 링크 => 1786번: 찾기 (acmicpc.net)

1786번: 찾기

---

KMP 문제이다.

 

KMP 란 Knuth Moriss Prett 의 약자로 긴 문자열 사이에 특정 문자열을 O(N+M) 만에 찾아내는 알고리즘이다. (긴 문자열 N, 특정 문자열 M)

 

접근하기에 앞서 Prefix, Suffix 에 대해 간단하게 알아보고 KMP 알고리즘 접근 방법에 대해 알아보도록 한다.

 

문자열 "abcde" 가 존재한다고 할 때

 

Prefix : a / ab / abc / abcd / abcde 로 맨 앞 문자부터 시작해서 끝나는 문자열을 의미한다.

 

Suffix : e / de / cde / bcde / abcde 로 Prefix 의 역이다.

 

KMP 알고리즘 접근 방법은 다음과 같다.

 

1. 비교하고자 할 문자열에 대하여 각 index 별로 Prefix와 Suffix의 길이가 동일할 때의 최대가 되는 값을 table 에다가 넣어준다.

 

문자열 S = "ababcab" 가 존재한다고 가정한다면 다음과 같은 순서로 table 를 채워갈 수 있다.

 

(1) 먼저 table 에 0 값으로 채워준다.

 

a	b	a	b	c	a	b
0	0	0	0	0	0	0

 

(2) 순서대로 Prefix, Suffix 를 비교해가며 값을 채워준다. (맨앞에 a는 생략)

 

b 부터 시작하도록 하며 table 에 채울 값으로 즉, Prefix 와 Suffix 의 길이가 최대가 되는 값 j = 0 이라 설정하고 문자열 S 를 접근하기 위한 인덱스 i = 1 이라 설정한다.

 

b 일때 Prefix (S[j] = a) 와 Suffix (S[i] = b) 가 동일하지 않으므로 그대로 j = 0

 

a	b	a	b	c	a	b
0	0	0	0	0	0	0

 

a 일때 Prefix (S[j] = a) 와 Suffix (S[i] = a) 가 동일하므로 j 값을 1 증가시켜서 j = 1 

 

a	b	a	b	c	a	b
0	0	1	0	0	0	0

 

b 일때 Prefix (S[j] = b) 와 Suffix (S[i] = b) 가 동일하므로 j 값을 1 증가시켜서 j = 2

 

a	b	a	b	c	a	b
0	0	1	2	0	0	0

 

c 일때 Prefix (S[j] = a) 와 Suffix (S[i] = c) 가 동일하지 않으므로 j = table[j - 1] 을 해줘서 다시 비교한다.

따라서 j = 0 이 되므로 Prefix (S[j] = a) 와 Suffix (S[i] = c) 가 동일하지 않으므로 그대로 j = 0

 

a	b	a	b	c	a	b
0	0	1	2	0	0	0

 

a 일때 Prefix (S[j] = a) 와 Suffix (S[i] = a) 가 동일하므로 j 값을 1 증가시켜서 j = 1

 

a	b	a	b	c	a	b
0	0	1	2	0	1	0

 

b 일때 Prefix (S[j] = b) 와 Suffix (S[i] = b) 가 동일하므로 j 값을 1 증가시켜서 j = 2

 

a	b	a	b	c	a	b
0	0	1	2	0	1	2

 

위 방법으로 table 을 채우는 code 는 다음과 같다.

void makeTable(char pattern[]) {
	memset(table, 0, cmpS_Len * sizeof(int));
	int j = 0;
	for (int i = 1; i < S_Len; i++) {
		while (j > 0 && pattern[i] != pattern[j]) {
			j = table[j - 1];
		}
		if (pattern[i] == pattern[j])
			table[i] = ++j;
	}
}

 

그렇다면 위에서 만든 Table 을 통해서 긴 문자열을 비교하기 위해서 다음 문자열이 존재한다고 가정하자.

 

S = "abaaababa" , cmpS = "aba" 

 

이때 비교하고자 할 문자열 cmpS 의 table = [ 0, 0, 1 ]

 

문자열 S를 인덱스 0 부터 시작하여 끝까지 비교해간다.

 

이때 문자열 S의 인덱스를 i = 0 이라 설정하고 비교하고자 할 문자열 cmpS 의 인덱스를 j = 0 이라 설정한다.

 

i = 0, j = 0 인 경우 => S[i] = cmpS[j] 이므로 j 값을 1 증가시킨다.

 

a	b	a	a	a	b	a	b	a
a

 

i = 1, j = 1 인 경우 => S[i] = cmpS[j] 이므로 j 값을 1 증가시킨다.

 

a	b	a	a	a	b	a	b	a
a	b

 

i = 2, j = 2 인 경우 => S[i] = cmpS[j] 이므로 j 값이 cmpS 의 모든 인덱스를 탐색하였으므로 S 문자열의 1번 문자에서 cmpS 문자열이 배치됨을 알 수 있다. 

 

a	b	a	a	a	b	a	b	a
a	b	a

그다음 문자열을 비교하기 위해서 j = table[j] 를 하여 j 값을 update 하고 다시 비교해간다.

이때 j = table[2] 이므로 j = 1 이다. 즉 cmpS 의 인덱스를 j = 1 부터 비교해가면 된다.

 

i = 3, j = 1 인 경우 => S[i] != cmpS[j] 이므로 j = table[j-1] 으로 update 해준다. (j = 0 으로 변경)

 

a	b	a	a	a	b	a	b	a
		a	b

 

i = 4, j = 0 인 경우 => S[i] = cmpS[j] 이므로 j 값을 1 증가시킨다.

 

a	b	a	a	a	b	a	b	a
				a

 

i = 5, j = 1 인 경우 => S[i] = cmpS[j] 이므로 j 값을 1 증가시킨다. 

 

a	b	a	a	a	b	a	b	a
				a	b

 

i = 6, j = 2 인 경우 => S[i] = cmpS[j] 이므로 j 값이 cmpS 의 모든 인덱스를 탐색하였으므로 S 문자열의 5번 문자에서 cmpS 문자열이 배치됨을 알 수 있다. 

 

a	b	a	a	a	b	a	b	a
				a	b	a

그다음 문자열을 비교하기 위해서 j = table[j] 를 하여 j 값을 update 하고 다시 비교해간다.

이때 j = table[2] 이므로 j = 1 이다. 즉 cmpS 의 인덱스를 j = 1 부터 비교해가면 된다.

 

i = 7, j = 1 인 경우 => S[i] = cmpS[j] 이므로 j 값을 1 증가시킨다. 

 

a	b	a	a	a	b	a	b	a
						a	b

 

i = 8, j = 2 인 경우 => S[i] = cmpS[j] 이므로 j 값이 cmpS 의 모든 인덱스를 탐색하였으므로 S 문자열의 7번 문자에서 cmpS 문자열이 배치됨을 알 수 있다. 

 

a	b	a	a	a	b	a	b	a
						a	b	a

 

따라서 문자열 cmpS 가 문자열 S 의 일부분이 될 경우 (i - j + 1) 번째에 배치됨을 알 수 있다. 

 

윗 방법으로 비교하는 code 이다.

void KMP(char parent[], char pattern[]) {
	int j = 0;
	for (int i = 0; i < S_Len; i++) {
		while (j > 0 && parent[i] != pattern[j]) j = table[j - 1];
		if (parent[i] == pattern[j]) {
			if (j == cmpS_Len - 1) {
				result[cnt++] = i - j + 1;
				j = table[j];
			}
			else j++;
		}
	}
}

 

풀이 code

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <vector>
#include <iostream>
#define endl '\n'

char S[1000002], cmpS[1000002];
int table[1000002], result[1000002];
int S_Len, cmpS_Len, cnt;

void makeTable(char pattern[]) {
	memset(table, 0, cmpS_Len * sizeof(int));
	int j = 0;
	for (int i = 1; i < cmpS_Len; i++) {
		while (j > 0 && pattern[i] != pattern[j]) {
			j = table[j - 1];
		}
		if (pattern[i] == pattern[j])
			table[i] = ++j;
	}
}

void KMP(char parent[], char pattern[]) {
	int j = 0;
	for (int i = 0; i < S_Len; i++) {
		while (j > 0 && parent[i] != pattern[j]) j = table[j - 1];
		if (parent[i] == pattern[j]) {
			if (j == cmpS_Len - 1) {
				result[cnt++] = i - j + 1;
				j = table[j];
			}
			else j++;
		}
	}
}

int main() {

	fgets(S, 1000002, stdin);
	fgets(cmpS, 1000002, stdin);

	S_Len = strlen(S) - 1;
	cmpS_Len = strlen(cmpS) - 1;

	makeTable(cmpS);
	KMP(S, cmpS);

	printf("%d\n", cnt);
	for (int i = 0; i < cnt; i++) {
		printf("%d\n", result[i]);
	}

	return 0;
}