fork(2) download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int dp[100];
  5. int t;
  6. string s;
  7.  
  8. // Implementation of KMP taken from stackoverflow
  9. int KMP(string S, string K)
  10. {
  11. vector<int> T(K.size() + 1, -1);
  12. vector<int> matches;
  13.  
  14. if(K.size() == 0)
  15. {
  16. matches.push_back(0);
  17. return 0;
  18. }
  19. for(int i = 1; i <= K.size(); i++)
  20. {
  21. int pos = T[i - 1];
  22. while(pos != -1 && K[pos] != K[i - 1]) pos = T[pos];
  23. T[i] = pos + 1;
  24. }
  25.  
  26. int sp = 0;
  27. int kp = 0;
  28. while(sp < S.size())
  29. {
  30. while(kp != -1 && (kp == K.size() || K[kp] != S[sp])) kp = T[kp];
  31. kp++;
  32. sp++;
  33. if(kp == K.size()) matches.push_back(sp - K.size());
  34. }
  35.  
  36. return matches.size();
  37. }
  38. bool searcher(int pos,int p1,int p2)
  39. {
  40. string s1,s2;
  41. for(int i=0; i<=pos; i++)
  42. s1+=s[i];
  43. for(int i=p1; i<=p2; i++)
  44. s2+=s[i];
  45. return KMP(s1,s2)>0;
  46. }
  47. void solve(void)
  48. {
  49.  
  50. for(int i=0; i<100; i++)
  51. dp[i]=i+1;
  52. dp[0]=1;
  53. for(int i=0; i<s.length()-1; i++)
  54. {
  55. dp[i+1]=min(dp[i+1],dp[i]+1);
  56. for(int j=1; i+j<s.length()&&j<=(i+1); j++)
  57. {
  58. if(searcher(i,i+1,i+j))
  59. {
  60. // cout << i << " " << j << endl;
  61. for(int k=i+1; k<s.length(); k++)
  62. {
  63. if(s[k]==s[i+1+(k-i-1)%j])
  64. {
  65. if((k-i)%j==0)
  66. dp[k]=min(dp[k],dp[i]+1+(k-i)/j);
  67. }
  68. else
  69. break;
  70. }
  71. }
  72. else
  73. break;
  74. }
  75. }
  76. }
  77. int main()
  78. {
  79. // freopen("input.in", "r", stdin);
  80. // freopen("output.out", "w", stdout);
  81. cin >> t;
  82. for(int i=1; i<=t; i++)
  83. {
  84. cin >> s;
  85. solve();
  86. cout << s << endl;
  87. printf("Case #%d: %d\n",i,dp[s.length()-1]);
  88. }
  89. return 0;
  90. }
  91.  
Success #stdin #stdout 0s 15240KB
stdin
Standard input is empty
stdout
Standard output is empty