const int N = 100;

int f[N][N];
char s[N + 1];

for (int i = n; i >= 0; i--)
  for (int j = n; j >= 0; j--)
    if (s[i] == s[j])
      LCP[i][j] = 1 + LCP[i + 1][j + 1];

// O(n^3 * logn), если вместо LCP сравнивать строки, получится n^4 logn
int go( int L, int R ) { // [L..R] O(n^2)
  ....
  f[L][R] = 1 + go(L+1, R);
  for (int T = 1; L + T <= R; T++)           // T * k <= R + 1
    for (int k = 2; L + T * k <= R + 1; k++) // O(nlogn)
      if (LCP[L][L + T] >= T*(k-1)) // O(1)
        f[L][R] = min(f[L][R], f[L][L+T-1] + 2 + len[k] + f[L+T*k][R])
  ...
}
// O(n^3)
int go( int L, int R ) { 
  ....
  f[L][R] = 1 + go(L+1, R);
  int len = R - L + 1;
  for (int M = L; M < R; M++)
    f[L][R] = min(f[L][R], f[L][M], f[M+1][R]);
  for (int T = 1; L + T <= R; T++)           
    if (len % T == 0 && LCP[L][L + T] >= len - T) // O(1)
      f[L][R] = min(f[L][R], f[L][L+T-1] + 2 + len[k])
  ...
}