CFR 825 F. String Compression
Problem Description:
Given string S, find the minimum length of its running length encoding.
Constraints:
1 ≤ len(S) ≤ 8000
Solution:
dp[i]: answer for S[0...i]
dp[j] = min(dp[i] + cost(i, j) for i in 0...j)
kmp[i]: maximum length of common prefix-suffix of S[0...i], excluding i
p[i...j]: length of minimum period of string S[i...j]
p[0...i] = i % (i - kmp[i]) == 0 ? i - kmp[i] : i
cost(0, j) = p[0...j] + int_len(j / p[0...j])
Simple recompute kmp array and cost functions for each left bound.
Code:
#include <bits/stdc++.h> void build_kmp(std::string::const_iterator ist, std::string::const_iterator ied, std::vector<int>::iterator ost) { std::vector<int>::iterator oit = ost; int ind = *oit = -1; for (std::string::const_iterator it = ist; it != ied; ++it) { while (~ind && *it != ist[ind]) ind = ost[ind]; *++oit = ++ind; } } int Dp(const std::string &s) { std::vector<int> dp(s.size() + 1, 0x3f3f3f3f); dp[0] = 0; std::vector<int> kmp(s.size() + 1); for (int i = 0; i < s.size(); ++i) { build_kmp(s.begin() + i, s.end(), kmp.begin() + i); for (int j = i + 1; j <= s.size(); ++j) { int plen = (j - i) % (j - i - kmp[j]) == 0 ? j - i - kmp[j] : j - i; std::function<int(int)> get_len = [&](int x) { for (int i = 0, j = 1; ; ++i, j *= 10) { if (x < j) return i; } }; dp[j] = std::min(dp[j], dp[i] + plen + get_len((j - i) / plen)); } } return dp[s.size()]; } signed main() { std::ios::sync_with_stdio(false); std::string S; std::cin >> S; std::cout << Dp(S) << std::endl; return 0; }