---

tags: codeforces, tutorial

---

# [Codeforces 825F String Compression](https://codeforces.com/contest/825/problem/F)

KMP求最小循環節 + DP

## Solution
假設string = $a_1a_2a_3...a_{n}$

定義 $f(i)$ 表示前i個字元壓縮後的最小長度
$i \in [0, n]$, base case $f(0) = 0$

$cir{i, j}$表示$a_ja_{j+1}...a_i$ substring的最小循環節長。
$slen( x )$ 表示$x$值的十進位長度
由此我們可以寫出轉移式

$f(i) = min\{ f(i - j) + cir(i-j, i) + slen(cir(i-j, i)) \}$

### $cir$ part

對於一個string求循環節長
我們可以利用kmp algorithm的prefix function

:::info
這邊的prefix function
使用這個定義
:::

位置$i$, $i \in [0, n)$
如果 `(i+1) % ((i+1) - prefix[i]) == 0`
則substring $a_1a_2a_3...a_{i+1}$ 的最小循環字串長度即為`(i+1) - prefix[i]`

## sol

如果我們寫成最直覺的recurrence

for i = 0 to n-1 // O(n)
	for j = 0 to i // O(n)
		求substr(i-j, i)的 prefix function // O(n)
		f(i) <- min(f(i), f(i-j)+cir(i-j, i)+slen())

表格大小為$O(n)$
每次轉移要花$O(n\times n)$

但可以觀察到
壓縮字串的時候，如果開頭一樣，是共用同樣的prefix function
因此我們可以改寫成下列的方式

for i = 0 to n-1 // O(n)
	求substr(i, n-1)的 prefix function
	for j = i to n
		f(j) <- min(f(j), f(i)+cir(i, j) + slen())

整體時間複雜度為$O(n^2)$

## Code

#include <bits/stdc++.h>
using namespace std;
const int inf = 2000000000;

int prefix[8000] = {0};
int dp[8001];
void gen_prefix(char* str, int len){
  prefix[0] = 0;
  for(int i = 1; i < len; i++){
    int len = prefix[i-1];
    while(len > 0 && str[len] != str[i]){
      len = prefix[len-1];
    }
    if(str[len] == str[i])
      len++;
    prefix[i] = len;
  }
}
int tostrlen(int val){
  if(val == 0)
    return 1;
  int ans = 0;
  while(val > 0)
    val /= 10, ans++;
  return ans;
}
int main(){
  char str[8000];
  scanf("%s", str);
  int len = strlen(str);
  fill(dp, dp+len+1, inf);
  dp[0] = 0;
  for (int i = 0; i < len; i++){
    gen_prefix(str + i, len - i);
    for (int j = i + 1; j <= len; j++){
      int curlen = j - i;
      int circulen = curlen - prefix[curlen-1];
      int circutime = curlen / circulen;
      if(curlen % circulen == 0 && circutime > 1){
        dp[j] = min(dp[j], dp[i] + circulen + tostrlen(circutime));
      }
      else{
        dp[j] = min(dp[j], dp[i] + curlen + 1);
      }
    }
  }
  cout << dp[len] << endl;

  return 0;
}