Educational Codeforces Round 25: F. String Compression
http://codeforces.com/contest/825/problem/F
解法
文字列の最小周期はKMP法のテーブルを用いて計算できる。kmp[i]
は文字列 S の先頭 i 文字を切り出した文字列の prefix と suffix の最大共通部分である。たとえば aabaabaab という文字列ならば 6 である。
aabaabaab ****** ******
もし文字列に周期があるならば、i-kmp[i]が最小の周期になる。これはよく考えると分かるだろう。逆に文字列に周期がないならば、iはi-kmp[i]の倍数にはならない。
KMPテーブルの計算はO(n)でできるため、全体でO(n^2)で解くことができた。
#include <iostream> #include <algorithm> #include <vector> #include <string> int main() { std::string s; std::cin >> s; const int n = s.size(); std::vector<int> len(n + 1); for (int i = 1; i <= n; i++) { len[i] = len[i / 10] + 1; } std::vector<int> dp(n + 1, 1e9); std::vector<int> kmp(n + 1); dp[0] = 0; for (int i = 0; i < n; i++) { kmp[i] = -1; int u = -1; for (int j = i + 1; j <= n; j++) { while (u != -1 && s[j - 1] != s[i + u]) u = kmp[i + u]; if (u == -1) { kmp[j] = u = 0; } else { kmp[j] = ++u; } int period = (j - i) - kmp[j]; if ((j - i) % period != 0) { period = j - i; } dp[j] = std::min(dp[j], dp[i] + len[(j - i) / period] + period); } } std::cout << dp[n] << std::endl; }