fork(1) download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const long long INF = 1e9;
  5. const int MAX_N = 105;
  6.  
  7. int T, N;
  8. char S[MAX_N];
  9. int Z[MAX_N][MAX_N], f[MAX_N][MAX_N];
  10. long long dp0[MAX_N], dp[MAX_N][MAX_N][MAX_N];
  11.  
  12. inline void imin(long long &x, long long y) {
  13.     x = min(x, y);
  14.     x = min(x, INF);
  15. }
  16.  
  17. int solve() {
  18.     for(int i=0; i<=N; i++) for(int j=0; j<=N; j++) for(int k=0; k<=N; k++)
  19.         dp[i][j][k] = INF;
  20.     for(int i=0; i<=N; i++)
  21.         dp0[i] = INF;
  22.  
  23.     dp0[0] = 0;
  24.     for(int i=1; i<=N; i++) {
  25.         int x, y;
  26.  
  27.         // paste some substring S[j,i]
  28.         for(int j=1; j<=i; j++) {
  29.             x = f[j][i], y = x + i-j;
  30.             imin(dp[i][x][y], dp[j-1][x][y] + 1);
  31.             imin(dp0[i], dp[i][x][y]);
  32.         }
  33.  
  34.         // type char S[i]
  35.         imin(dp0[i], dp0[i-1] + 1);
  36.         for(int j=1; j<i; j++) for(int k=1; k<=j; k++)
  37.             imin(dp[i][k][j], dp[i-1][k][j] + 1);
  38.  
  39.         // update
  40.         for(int j=1; j<=i; j++) for(int k=1; k<=j; k++)
  41.             imin(dp[i][k][j], dp0[i] + 1);
  42.  
  43.     }
  44. }
  45.  
  46. // codeforces.com/blog/entry/3107
  47. void setZ() {
  48.     for(int st=1; st<=N; st++) {
  49.         int L = st, R = st;
  50.         Z[st][st] = N - st + 1;
  51.         for(int i=st+1; i<=N; i++) {
  52.             if(i>R) {
  53.                 L = R = i;
  54.                 while(R<=N && S[st+R-L]==S[R]) R++;
  55.                 Z[st][i] = R - L; R--;
  56.             }
  57.             else {
  58.                 int k = st + i - L;
  59.                 if(Z[st][k]<R-i+1) Z[st][i] = Z[st][k];
  60.                 else {
  61.                     L = i;
  62.                     while(R<=N && S[st+R-L]==S[R]) R++;
  63.                     Z[st][i] = R - L; R--;
  64.                 }
  65.             }
  66.         }
  67.     }
  68. }
  69.  
  70. void setf() {
  71.     for(int i=1; i<=N; i++) for(int j=1; j<=i; j++) {
  72.         for(int st=j; st>=1; st--)
  73.             if(Z[st][j] >= i-j+1)
  74.                 f[j][i] = st;
  75.     }
  76. }
  77.  
  78. int main() {
  79.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  80.  
  81.     cin >> T;
  82.     for(int t=1; t<=T; t++) {
  83.         cin >> S+1;
  84.         N = strlen(S+1);
  85.  
  86.         setZ();
  87.         setf();
  88.         solve();
  89.  
  90.         cout << "Case #" << t << ": " <<dp0[N] << "\n";
  91.     }
  92.     return 0;
  93. }
Success #stdin #stdout 0s 24368KB
comments (?)
stdin 
1
abcdxabcdyabcd
stdout 
Case #1: 9
https://ideone.com/MJBmTT
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!