题意

给出一个字符串，你要把它尽量压缩成一个短的字符串，比如一个字符串ababab你可以转化成3ab，长度为 3，比如bbbacacb转化成3b2ac1b，长度为 7，aaaaaaaaaa转化为10a，长度为 3。

分析

求转换后的最短字符串，那么怎么去组合字符串中的子串是关键。

考虑 dp，dp[1...L] 对应字符串 S[0...L-1] 。dp[i] 表示字符串 S[0, i - 1] 转化后的字符串长度，dp[0] = 0。

状态转移方程：$ dp[i] = min(dp[i], dp[j] + has[j][i - 1]) $，其中 \(has[j][i - 1]\) 表示字符串 S[j, i - 1] 由某个字符（串）重复 k 次，k 取最大的时候，转化后的长度。比如abab，ab重复了两次，那么 \(has\) 的值为 3。

那么我们就要去预处理 has 的值，一个字符串（长度为 L）由 k 个连续且相同的子串组成，求 k 的最大值。这个问题不就是某个经典的字符串题吗？

当然不用后缀数组那么麻烦，那只是为了练习 : ) 。

考虑 KMP 算法中 nxt 数组的含义，对于字符串abcabc，那么 \(nxt[6] = 3\)，即前缀后缀相同的子串长，我们称最小连续的那个子串为循环节，设 \(l = L - nxt[L]\)，如果 \(l\) 刚好整除 \(L\)，那么 \(l\) 就是循环节的长度。对于字符串ababab， \(nxt[6]=4\) ，假如后面还有字符，第 7 个字符导致失配，最后的四个字符abab不用再去匹配了，直接由abab向后匹配，正好是右移了一个循环节的位置。

code

#include
    
     using namespace std;const int MAXN = 8000 + 10;const int INF = 1e9;char T[MAXN];int nxt[MAXN];void getNext() {    int tlen = strlen(T);    int j, k;    j = 0;    k = -1;    nxt[0] = -1;    while(j < tlen)        if(k == -1 || T[j] == T[k])            nxt[++j] = ++k;        else            k = nxt[k];}int getl(int x) {    int cnt = 0;    while(x) {        cnt++;        x /= 10;    }    return cnt;}char S[MAXN];int dp[MAXN];int has[MAXN][MAXN];int main() {    scanf("%s", S);    int L = strlen(S);    for(int i = 0; i < L; i++) {        has[i][i] = 2;        int l = 0;        for(int j = i; j < L; j++) {            T[l++] = S[j];        }        T[l] = 0;        getNext();        l = 0;        for(int j = i + 1; j < L; j++) {            l++;            int k = j - i + 1;            int p = k - nxt[l + 1];            if(k % p == 0) {                has[i][j] = getl(k / p) + p;            } else has[i][j] = j - i + 2;        }    }    dp[0] = 0; // dp[1..L] 对应字符串 S[0..L-1]    for(int i = 1; i <= L; i++) {        dp[i] = i + 1;        for(int j = 0; j < i; j++) {            // [j + 1, i] 对应字符串的 [j, i - 1]            dp[i] = min(dp[i], dp[j] + has[j][i - 1]);        }    }    printf("%d\n", dp[L]);    return 0;}