fork(3) download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DgynCm
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

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!