티스토리 뷰
문제
알파벳 소문자로만 이루어진 문자열이 주어진다. 부분문자열의 "등장값" 이란 그 부분문자열이 등장하는 횟수와 부분문자열의 길이를 곱한 값이다. 문자열이 주어졌을 때, 팰린드롬이면서 가장 큰 등장값을 가지는 부분문자열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 알파벳 소문자(a-z)로만 이루어진 문자열이 주어진다. 문자열의 길이는 300,000보다 작거나 같다.
출력
첫째 줄에 팰린드롬인 부분문자열 중에서 가장 큰 등장값을 출력한다.
예제 입력
abacaba
예제 출력
7
풀이
이 문제는 접미사 배열과 lcp, manacher 알고리즘을 모두 사용하는 문제이다. 어떤 자료구조를 사용하느냐에 따라 시간복잡도가 $\BigO{N\log^{2}N}$이 되기도 하고, $\BigO{N\log{N}}$이 되기도 한다.
팰린드롬이 아니라 모든 부분문자열에 대해서 가장 큰 등장값을 구하는 문제를 풀 수 있을까? 접미사 배열에서 lcp들을 구한 뒤에 모든 구간에 대해서 (구간 길이)\(\times\)(구간 내에서 lcp 최솟값)의 최댓값을 구하면 된다. (구간 길이는 어떤 부분 문자열이 나타나는 횟수이고 구간 내에서 lcp 최솟값은 그 구간에서 등장할 수 있는 부분문자열의 최대 길이이다.) 이 문제는 스택을 이용하여 $\BigO{N}$에 풀 수도 있고 분할 정복이나 RMQ를 사용해 $\BigO{N\log{N}}$에 해결할 수도 있다. 이 문제는 너무 유명하기 때문에 풀이는 생략한다. 혹시 풀이를 모른다면 스스로 생각해보기 바란다.
이제 부분문자열이 팰린드롬이라는 조건을 추가하여 문제를 풀어보자. Manacher 알고리즘으로 구한 N개의 팰린드롬을 생각해보면, 팰린드롬을 중심축을 기준으로 왼쪽을 버리고 오른쪽만 저장해도 각각의 팰린드롬을 구별하는 데 지장이 없음을 알 수 있다. 이 반쪽 팰린드롬들을 사전순으로 정렬하면 앞의 문제와 똑같은 방법으로 답을 구할 수 있다.
여기서 풀어야 할 문제는 반쪽 팰린드롬을 사전순으로 정렬한 후 이 배열의 lcp를 구하는 것이다. 반쪽 팰린드롬 배열은 접미사 배열의 각 문자열에서 반쪽 팰린드롬에 포함되지 않는 뒷부분 얼마를 잘라낸 것을 사전순으로 정렬한 것이다. 접미사 배열에서 조금만 변형을 가하면 되므로 접미사 배열을 구한 방법을 사용할 수 있을까? 안타깝게도 할 수가 없다. 접미사 배열 때와는 달리 문자열을 sz만큼 비교한 결과를 가지고 2sz만큼 비교한 결과를 알 수 없기 때문이다. 뒤에 문자열이 얼마나 잘려 있는지 알 수가 없는 것이 큰 문제이다. S[i\(\cdots\)]와 S[i+sz\(\cdots\)]가 뒷부분이 잘려있는 길이가 다를 수 있어서 함부로 이를 이용할 수 없다.
먼저 팰린드롬을 정렬한 배열이 주어졌을 때, lcp를 구하는 방법을 생각해보자. 이전에 접미사 배열에서 lcp를 구한 것처럼 $\BigO{N}$에 lcp를 계산하는 것은 불가능하다. 그 방법을 그대로 사용하면 문제가 발생한다. lcp가 반복문 내에서 매번 1이하로 감소해야 선형 시간에 작동함이 보장이 되는데 팰린드롬은 원래 접미사보다 길이가 작을 수 있어서 lcp가 팰린드롬의 길이보다 클 경우 lcp를 줄여주어야 한다. 이 때문에 lcp가 많이 줄어들고 많이 증가할 수 있어서 선형시간에 구할 수가 없다.
lcp를 어떤 상황에서도 $\BigO{N\log{N}}$에 구하는 다른 방법을 생각해 보자. 임의의 두 접미사의 lcp는 접미사 배열에서 두 접미사 사이의 lcp값들 중 최솟값이다. 이를 세그먼트 트리를 사용하면 로그시간에 확인할 수 있다. 모든 부분문자열은 접미사의 접두사이기 때문에 임의의 두 부분문자열의 lcp는 그 부분문자열이 접두사인 접미사의 lcp를 통해 알 수 있다. (만약 그 lcp값이 부분문자열 길이보다 크면 부분문자열의 길이로 줄여주면 된다.) 이것을 이용하면 팰린드롬을 빠르게 정렬할 수 있다. 두 부분문자열의 대소관계를 확인하려면 lcp를 구한 다음에 공통되는 부분이 아닌 다음 문자를 비교하면 되므로 로그시간이 든다. cmp함수를 따로 작성하여 std::sort를 사용하면 $\BigO{N\log^{2}{N}}$에 팰린드롬을 정렬한 배열을 구할 수 있고 lcp를 $\BigO{N\log{N}}$에 구할 수 있으므로 답을 $\BigO{N\log^{2}{N}}$에 구할 수 있다.
이제 $\BigO{N\log{N}}$으로 시간복잡도를 줄여보자. sparse table을 사용하면 전처리에 $\BigO{N\log{N}}$, 구간 내 최솟값을 찾는데 $\BigO{1}$이 걸린다. 이러면 lcp값을 상수시간에 확인할 수 있어서 $\BigO{N\log{N}}$만에 답을 구할 수 있다.
또 다른 풀이도 있는데 이 풀이는 한 가지 간단한 사실을 아는 것으로부터 시작된다. 그것은 바로 Manacher 알고리즘으로 구한 N개의 팰린드롬 중에서만 답이 되는 팰린드롬이 있다는 것이다. (N개의 팰린드롬에 포함되는 작은 팰린드롬은 결코 답이 될 수 없다는 것을 알 수 있을 것이다.) 그렇다면 접미사 배열에서 N개의 팰린드롬이 각각 얼마나 나타나는지 알아내는 것으로 답을 구할 수 있다. N개의 팰린드롬이 접두사인 접미사의 위치를 구한 다음에 lcp가 팰린드롬 길이 이상인 가장 위에 있는 접미사랑 가장 아래에 있는 접미사를 이분탐색으로 구하면 그 팰린드롬이 나타나는 빈도수를 알 수 있다. 이분탐색을 하는 중에 구간내 최소 lcp를 찾아내는 과정이 필요한데 여기서도 세그먼트 트리를 쓰면 $\BigO{N\log^{2}{N}}$, sparse table을 사용하면 $\BigO{N\log{N}}$에 구할 수 있다.
이외에도 해시를 사용하여 팰린드롬 트리를 만들어서 푸는 방법도 존재한다.
http://koosaga.myungwoo.kr/entry/%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC-APIO-2014
'문자열' 카테고리의 다른 글
| 접미사 배열 (0) | 2017.02.20 |
|---|---|
| 팰린드롬 (0) | 2017.02.20 |
| AhoCorasick (0) | 2017.02.17 |
| KMP (0) | 2017.02.17 |