fork 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
stdin
1
abcdxabcdyabcd
stdout
Case #1: 9