백준 1701 / Cubeditor / 문자열, KMP / JAVA

오늘 살펴볼 문제는 백준 1701 <Cubeditor> 문제이다.

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

1701번: Cubeditor

이 문제는 문자열 처리 관련된 유형으로 KMP 알고리즘을 사용하여 문제를 풀어야 시간 내에 맞힐 수 있다. ACM-ICPC 서울 리지널 기출문제이며, 난이도는 골드 2이다. 쉬운 문제는 아니지만 KMP 알고리즘에 대한 이해가 있다면 아이디어를 떠올리는데 도움을 받을 수 있을 것이다.

먼저 문제를 풀기 앞서서 KMP 알고리즘에 대해 살펴보고 가자.

KMP 알고리즘은 어떤 문자열 안에 특정 문자열이 몇 개나 있는지를 찾는 알고리즘이다. 예를 들어 ABCDABC 안에 ABC는 2개가 있다는 것을 찾아내는 것이다. 일반적인 방법이라면 길이가 N인 문자열에서 길이가 M인 특정 문자열을 찾는다면 하나씩 다 탐색을 해볼 수 있고 결과적으로 M개의 문자열을 N번씩 탐색해 주어야 해서 O(NM)의 시간 복잡도가 나오게 된다. 쉽게 생각할 수 있지만 시간이 너무 오래 걸린다.

그래서 이 문제를 O(M+N)의 시간복잡도로 풀 수 있는 방법을 Knuth, Morris, Prett이 고안해 냈는데, 이들의 이름 앞글자를 따서 KMP 알고리즘이라고 부른다. KMP 알고리즘은 접두사와 접미사 정보를 기억해서 가능성이 있는 문자열만 껑충껑충 뛰면서 탐색하는 방법이다.

먼저 이 문제를 풀기 위해서 pi[]라는 하나의 배열을 만들어야 하는데, pi[i]에는 주어진 문자열의 인덱스 0부터 인덱스 i까지의 부분 문자열 중에서 접두사 == 접미사가 되는 가장 긴 접두사의 길이를 넣는다. 예를 들면 문자열 ABAABA의 pi를 구한다고 하면 다음과 같다.

그러면 이제 KMP 알고리즘이 어떻게 동작하는지를 한 번 보도록 하자. ABABAABABAABA 라는 문자열에서 ABAABA가 얼마나 있는지 찾는다고 가정한다. 우리가 이전에 사용했던 방법대로라면 처음에 ABAABA가 아니기 때문에 한 칸씩 이 문자열을 이동하면서 모든 문자들을 탐색할 것이다.

KMP 알고리즘에서는 중복된 부분 정보를 버리지 않고 사용한다. 이 예시에서는 앞에 ABA가 중복된다. 앞서 구했던 pi에서 pi[1] 이다. ABA 에서 한 글자가 문자열의 앞 뒤에서 같은 것이다. 우리가 이 정보를 알고 있다면 바로 다음 단계로 뛰어 갈 수가 있다.

원래였으면 한칸을 더 연산했어야 하는데 그만큼 연산을 아낄 수 있었다. 이런식으로 그 다음 위치에서도 일치하는 문자열을 먼저 구한다. 여기서는 문자열 전체가 일치하므로 count++ 를 해주고 pi를 살펴본다. pi[5] = 3이다. ABAABA 이렇게 앞 뒤의 세 개 문자가 일치하며 따라서 이번에는 다음처럼 점프를 할 수 있게 된다.

이런식으로 KMP 알고리즘을 사용하면 문자열을 탐색할 때 가능성이 아예 없는 문자열은 빼고, 가능성이 있는 문자열 중심으로 빠르게 탐색할 수 있다. 이에 대한 이해를 바탕으로 오늘 풀어볼 문제를 살펴보자.

어떤 문자열이 주어지고 이 문자열에서 두 번 이상 나오는 부분 문자열 중에서 가장 길이가 긴 값을 구하는 것이다. 일단 전체 문자열에 대해서 Pi를 통해 가장 접두사 == 접미사 인 경우를 찾으면 최대 길이가 되는 경우도 있을 것이다. 마치 위에서 봤던 ABAABA 처럼 말이다. 두 문자열은 겹쳐도 상관이 없다. AAA 같은 문자열은 AA가 두 번 나오기 때문에 결과값이 2이다.

하지만 이렇게 전체 문자열 한 번에 대해서만 Pi를 구하면 ABBCBBA 와 같은 반례가 있다. 전체 문자열에 대해서는 접두사 == 접미사가 같은 최대 길이가 1인데 실제로는 BB가 두번 나와서 결과값은 2가 된다. 따라서 길이가 n인 어떤 문자열이 주어졌을 때 i = 0 부터 n-1 까지의 경우에 대해 인덱스가 i부터 n-1 까지인 모든 문자열에 대해서 Pi를 구해주고 각각의 최대값을 모두 구해서 그 중에 최대값을 리턴해야 한다.

아래는 내가 작성한 자바 소스코드이다.

문제가 쉽지는 않다고 생각한다. 하지만 KMP 알고리즘을 공부하면서 풀기에는 좋은 문제인 것 같아서 풀어보기를 권한다. ㅎㅎ