[알고리즘 정리] KMP(2/3)

pi 배열 생성하기

아래 함수는 이전 포스트에서 그림을 통해 그려본 pi 배열을 만드는 과정을 구현한 코드입니다.

static int[] getPi(String pattern) {
	int[] pi = new int[pattern.length()];
	char[] pt = pattern.toCharArray();

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

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

	return pi;
}

아래부터는 위 코드가 동작하는 과정을 그림으로 나타낸 것입니다.

j = 0, i = 1

pt[i]와 pt[j]가 다르므로 j가 감소해야 하지만, 더 이상 앞으로 갈 곳이 없으니 i만 전진합니다.

j = 0, i = 2

pt[i] 와 pt[j] 가 같으므로 pi[i] 에 j를 1 증가시킨 값인 1을 넣어줍니다.

j = 1, i = 3

pt[i]와 pt[j]가 같으므로 pi[i]에 j를 1 증가시킨 값인 2를 넣어줍니다.

j = 2, i = 4

pt[i]와 pt[j]가 같으므로 pi[i]에 j를 1 증가시킨 값인 2를 넣어줍니다.

j = 3, i = 5

pt[i]와 pt[j]가 다르므로 j가 맞는 위치를 찾아갑니다. 새로운 j는 pi[3-1]인 1이 됩니다.

j = 1, i = 5

pt[i]와 pt[j]가 다르므로 j가 맞는 위치를 찾아갑니다. 새로운 j는 pi[1-1]인 0이 됩니다.

j = 0, i = 5

pt[i]와 pt[j]가 다르므로 j가 감소해야 하지만, 더 이상 앞으로 갈 곳이 없으니 i만 전진합니다.

j = 0, i = 6

pt[i]와 pt[j]가 같으므로 pi[i]에 j를 1 증가시킨 값인 1을 넣어줍니다.

인덱스 i는 부분 문자열의 끝을 의미하게 됩니다. i가 3의 위치에 있으면, 부분 문자열 ABAB의 접두사 및 접미사의 최대 공통 길이를 구하여 pi[3] 에 저장하게 됩니다.

인덱스 j는 그 위치까지 맞아떨어진 접두사의 앞과 접미사의 앞의 문자 개수를 기억하고 있습니다. 따라서 pt[i] 와 pt[j] 만 같으면 접두사 및 접미사의 최대 공통 길이는 j가 기억하고 있는 개수(j 그 자체)에서 1 증가하게 되는 것입니다.