Pasted

#include <vector>
#include "optimization.h"
#include <cmath>
#include <cstring>
#include <cassert>
using namespace std;
char s[101], g[101];
int lcp[101][101] = {};
int ans[101][101] = {};
pair<int, int> p[101][101];
int get_lcp(size_t i, size_t j) {
    if(lcp[i][j] == -1) {
        if(s[i] == 0 || s[j] == 0 || s[i] != s[j]) {
            lcp[i][j] = 0;
        } else {
            lcp[i][j] = get_lcp(i+1, j+1) + 1;
        }
    }
    return lcp[i][j];
}
 
void fill_lcp(size_t n) {
    for (auto &row : lcp) {
        for (int &item : row) {
            item = -1;
        }
    }
    for (int i = 0; i <= n; ++i) {
        for(size_t j = 0; j <= n; j++) {
            get_lcp(i, j);
        }
    }
 
}
 
bool relax(int& a, int v) {
    if(a > v) {
        a = v;
        return true;
    }
    return false;
}
 
int length(int k) {
    if(k == 0) return 1;
    int ret = 0;
    while(k > 0) {
        ret++;
        k /= 10;
    }
    return ret;
}
 
int get_ans(int i, int len) {
    if(ans[i][len] == -1) {
        ans[i][len] = len;
        p[i][len] = {-1, 0};
        for(int m = 1; m < len; m++) {
            if(relax(ans[i][len], get_ans(i, m) + get_ans(i+m, len-m))) {
                p[i][len] = {0, m};
            }
            if (len % m == 0 && lcp[i][i + m] >= len - m) {
                if(relax(ans[i][len], length(len / m) + get_ans(i, m) + 2)) {
                    p[i][len] = {1, m};
                }
            }
        }
    }
    return ans[i][len];
}
 
void restore(int i, int len, int o) {
    auto [type, m] = p[i][len];
    if(type == -1) {
        for(int j = 0; j < len; j++) {
            g[o+j] = s[i+j];
        }
    } else if(type == 0) {
        int a = get_ans(i, m);
        restore(i, m, o);
        restore(i+m, len-m, o+a);
    } else if(type == 1) {
        int count = len / m;
        int clen = length(count);
        for(int k = clen - 1; k >= 0; k--) {
            g[o + k] = (char) ('0' + (count % 10));
            count /= 10;
        }
        g[o+clen] = '(';
        restore(i, m, o+clen+1);
        g[o+clen+1+get_ans(i, m)] = ')';
    } else {
        assert(false);
    }
}
 
int main() {
    readWord(s);
    size_t n = strlen(s);
    fill_lcp(n);
    for (auto &row : ans) {
        for(auto &item : row) {
            item = -1;
        }
    }
    get_ans(0, n);
    restore(0, n, 0);
    writeWord(g);
    return 0;
}