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[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;
}