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