팰린드롬 분할

문제 링크

Manacher Algorithm을 반드시 알아야 풀 수 있는 문제다. 모르는 상태에서도 곰곰히 생각해보면 길이가 2500인 문자열을 $O(N^3)$ 알고리즘으로 검사해야 하는데 이것은 시간상 불가능하므로 별도의 알고리즘이 필요하다는 사실을 짐작할 수 있다.

발상

Manacher Algorithm을 통해 문자열의 각 인덱스 별로 해당 인덱스를 중심으로 하는 가장 긴 팰린드롬의 길이를 구했다. 모든 위치에서 가장 긴 팰린드롬의 길이를 알 수 있으므로 현재 문자열 $S$에서 팰린드롬 문자열을 뺀 이전 문자열 $S^{\prime }$들을 알아낼 수 있다. 그리고 재귀적으로 다시 문자열 $S^{\prime }$에서 팰린드롬 문자열을 뺀 이전 문자열 $S^{\prime \prime }$들을 알 수 있다. 이런식으로 계속 팰린드롬 문자열을 빼나가다보면 빈 문자열에 도달할 것이다. 빈 문자열은 기저사례가 된다. 빈 문자열은 0개의 팰린드롬 문자열로 이루어져 있으며, 팰린드롬 문자열을 뺄 때 마다 이전 문자열 $S^{\prime }$를 구성하는 팰린드롬 문자열 수 + 1을 하면 $S$의 팰린드롬 분할 수 를 알 수 있다. 그림으로 나타내면 아래와 같다. 위 그림에서 $S^{\prime }1$, $S^{\prime }2$, $S^{\prime }3$ 부분 문자열에서 다시 재귀적으로 팰린드롬 문자열을 찾아내는 과정을 반복한다. 그 후 그 중 가장 작은 팰린드롬 문자열 수에 1을 더한 값이 현재 문자열 $S$를 만드는데 필요한 최소 팰린드롬 분할 수다.

점화식

$$\{\begin{array}{l}{n}_i=\text{문자열 인덱스 0∼i까지의 최소 팰린드롬 분할 수}\\ p_i=\text{인덱스 i를 중심으로 하는 최장 팰린드롬 길이}\end{array}$$ $$n_i=\underset{j=0\to i-1}{\min }(\{\begin{array}{ll}{n}_{2j-i-1}& \text{if i−j≤pj}\end{array})+1$$

$n_{2j-i-1}$이 그림의 $S^{\prime }1$, $S^{\prime }2$, $S^{\prime }3$ 세 부분 문자열의 마지막 인덱스를 계산한 항이다. 팰린드롬 중심 인덱스 $j$에서 현재 인덱스 $i$와의 차이만큼 이전으로 이동한 인덱스 $=j-(i-j)-1=2j-i-1$으로 유도된다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int main()
{
	string s, sp = "#"; cin >> s;
	for (int i = 0; i < s.size(); i++) {
        sp.push_back(s[i]); sp.push_back('#');
	}
    int n = sp.size(); vector<int> res(n);
	int p, r = -1;
    // manacher algorithm
    for (int i = 0; i < n; i++) {
        if (i > r) {
            p = r = i;
            while (r < n && r <= 2 * p && sp[r] == sp[2 * p - r]) r++;
            r--;
            res[i] = r - p;
        }
        else {
            int j = 2 * p - i;
            if (res[j] < r - i) {
                res[i] = res[j];
            }
            else if (res[j] > r - i) {
                res[i] = r - i;
            }
            else {
                p = i;
                while (r < n && r <= 2 * p && sp[r] == sp[2 * p - r]) r++;
                r--;
                res[i] = r - p;
            }
        }
    }
    vector<int> dp(n + 1, (int)21e8); // dp[i] = 인덱스 i까지 최소 팰린드롬 분할 수 
    dp[0] = 0; dp[1] = 0; dp[2] = 1; // 첫 문자까지 기저 사례 취급
    for (int i = 3; i <= n; i++) {        
        dp[i] = dp[i - 1] + (sp[i - 1] != '#' ? 1 : 0); // 보강용 문자는 실재하는 문자는 아니므로 끝에 추가돼도 분할 수가 늘어나지는 않는다.
        for (int j = 2; j < i; j++) {
            if (i - j <= res[j - 1]) {
                dp[i] = dp[i] < dp[j - (i - j) - 1] + 1 ? dp[i] : dp[j - (i - j) - 1] + 1;
            }
        }
    }
    cout << dp[n];
	return 0;
}