fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  5.  
  6. #define ll long long
  7. #define ull unsigned long long
  8. #define ld long double
  9. #define pb push_back
  10. #define eb emplace_back
  11. #define mp make_pair
  12. #define fi first
  13. #define se second
  14.  
  15. #define sz(v) ((int)(v).size())
  16. #define all(v) (v).begin(), (v).end()
  17. #define rall(v) (v).rbegin(), (v).rend()
  18. #define clr(v, d) memset(v, d, sizeof(v))
  19.  
  20. #define forn(i, e) for (int i = 0; i < e; i++)
  21. #define fors(i, s, e) for (int i = s; i < e; i++)
  22. #define rforn(i, s) for (int i = s; i >= 0; i--)
  23. #define rfors(i, s, e) for (int i = s; i >= e; i--)
  24.  
  25. #define msb(x) (63 - __builtin_clzll((unsigned long long)(x)))
  26. #define lsb(x) (__builtin_ctzll((unsigned long long)(x)))
  27. #define bit_count(x) (__builtin_popcountll((unsigned long long)(x)))
  28.  
  29. #ifndef ONLINE_JUDGE
  30. #define debug(x) cerr << #x << " = " << (x) << '\n';
  31. #else
  32. #define debug(x)
  33. #endif
  34.  
  35. typedef vector<int>       vi;
  36. typedef vector<double>    vd;
  37. typedef vector< vi >      vvi;
  38. typedef vector< vd >      vvd;
  39. typedef vector<string>    vs;
  40.  
  41. const int INF = 1e9 + 7;
  42. const ll LINF = 1e18 + 7;
  43. const double EPS = 1e-9;
  44. const int MAXN = 8005;
  45. const int LOG = 20;
  46. // #define int ll
  47.  
  48. const int dx[] = {-1, 1, 0, 0, -1, -1, 1, 1};
  49. const int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
  50.  
  51.  
  52. const ll MOD1 = 1e9 + 7;
  53. const ll MOD2 = 998244353;
  54. ll BASE1 = 31, BASE2 = 37;
  55.  
  56. ll pw1[MAXN], pw2[MAXN], inv1[MAXN], inv2[MAXN];
  57. int spf[MAXN];
  58.  
  59. ll fastPow(ll x, ll y, ll m) {
  60.     x %= m;
  61.     ll res = 1;
  62.     while (y > 0) {
  63.         if (y & 1) res = (res * x) % m;
  64.         x = (x * x) % m;
  65.         y >>= 1;
  66.     }
  67.     return res;
  68. }
  69.  
  70. ll modInv(ll x, ll m) {
  71.     return fastPow(x, m - 2, m);
  72. }
  73.  
  74. void init_hash() {
  75.     mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  76.     BASE1 = uniform_int_distribution<ll>(300, 1000)(rng) | 1;
  77.     do {
  78.         BASE2 = uniform_int_distribution<ll>(300, 1000)(rng) | 1;
  79.     } while (BASE1 == BASE2);
  80.  
  81.     pw1[0] = pw2[0] = inv1[0] = inv2[0] = 1;
  82.     ll inv_b1 = modInv(BASE1, MOD1);
  83.     ll inv_b2 = modInv(BASE2, MOD2);
  84.  
  85.     for (int i = 1; i < MAXN; i++) {
  86.         pw1[i] = (pw1[i - 1] * BASE1) % MOD1;
  87.         pw2[i] = (pw2[i - 1] * BASE2) % MOD2;
  88.         inv1[i] = (inv1[i - 1] * inv_b1) % MOD1;
  89.         inv2[i] = (inv2[i - 1] * inv_b2) % MOD2;
  90.     }
  91. }
  92.  
  93. struct StringHash {
  94.     int n;
  95.     string s;
  96.     vector<pair<ll,ll>> pref, rev_pref;
  97.  
  98.     StringHash(const string &_s) : s(_s), n(_s.size()) {
  99.         pref.resize(n);
  100.         rev_pref.resize(n);
  101.  
  102.         for (int i = 0; i < n; i++) {
  103.             ll val1 = s[i] - 'a' + 1;
  104.             ll val2 = s[n - 1 - i] - 'a' + 1;
  105.  
  106.             if (i == 0) {
  107.                 pref[i] = {val1, val1};
  108.                 rev_pref[i] = {val2, val2};
  109.             } else {
  110.                 pref[i].first = (pref[i - 1].first * BASE1 + val1) % MOD1;
  111.                 pref[i].second = (pref[i - 1].second * BASE2 + val1) % MOD2;
  112.  
  113.                 rev_pref[i].first = (rev_pref[i - 1].first * BASE1 + val2) % MOD1;
  114.                 rev_pref[i].second = (rev_pref[i - 1].second * BASE2 + val2) % MOD2;
  115.             }
  116.         }
  117.     }
  118.  
  119.     pair<ll,ll> get_hash(int l, int r) {
  120.         if (l > r) return {0, 0};
  121.         if (l == 0) return pref[r];
  122.         int len = r - l + 1;
  123.         ll h1 = (pref[r].first - (pref[l - 1].first * pw1[len]) % MOD1 + MOD1) % MOD1;
  124.         ll h2 = (pref[r].second - (pref[l - 1].second * pw2[len]) % MOD2 + MOD2) % MOD2;
  125.         return {h1, h2};
  126.     }
  127.  
  128.     pair<ll,ll> get_rev_hash(int l, int r) {
  129.         if (l > r) return {0, 0};
  130.         int rl = n - 1 - r;
  131.         int rr = n - 1 - l;
  132.         if (rl == 0) return rev_pref[rr];
  133.         int len = rr - rl + 1;
  134.         ll h1 = (rev_pref[rr].first - (rev_pref[rl - 1].first * pw1[len]) % MOD1 + MOD1) % MOD1;
  135.         ll h2 = (rev_pref[rr].second - (rev_pref[rl - 1].second * pw2[len]) % MOD2 + MOD2) % MOD2;
  136.         return {h1, h2};
  137.     }
  138.  
  139.     bool is_palindrome(int l, int r) {
  140.         return get_hash(l, r) == get_rev_hash(l, r);
  141.     }
  142. };
  143.  
  144.  
  145. int get_digits(int x) {
  146.     if (x < 10) return 1;
  147.     if (x < 100) return 2;
  148.     if (x < 1000) return 3;
  149.     if (x < 10000) return 4;
  150.     return 5;
  151. }
  152.  
  153. void solve() {
  154.     string s; cin >> s;
  155.     int n = s.size();
  156.     StringHash h(s);
  157.  
  158.     for (int i = 2; i <= n; i++)
  159.         if (!spf[i])
  160.             for (int j = i; j <= n; j += i)
  161.                 if (!spf[j]) spf[j] = i;
  162.  
  163.     vector<int> min_dp(n + 2, INF);
  164.  
  165.  
  166.  
  167.     for (int i = n; i >= 1; i--) {
  168.         int best = INF;
  169.         for (int len = 1;len <= n-i+1;len++) {
  170.             int a = i - 1, b = i + len - 2;
  171.             int p = len, x = len;
  172.  
  173.             while (x > 1) {
  174.                 int q = spf[x];
  175.                 while (x % q == 0) x /= q;
  176.                 while (p % q == 0) {
  177.                     int d = p / q;
  178.                     if (h.get_hash(a, b - d) == h.get_hash(a + d, b)) p = d;
  179.                     else break;
  180.                 }
  181.             }
  182.             int cost = get_digits(len / p) + p;
  183.             int rem = (i + len > n) ? 0 : min_dp[i + len];
  184.             best = min(best, cost + rem);
  185.         }
  186.         min_dp[i] = best;
  187.     }
  188.  
  189.  
  190.     cout << min_dp[1] << endl;
  191.  
  192. }
  193.  
  194.  
  195. signed main() {
  196. #ifndef ONLINE_JUDGE
  197.     // freopen("feast.in", "rt", stdin);
  198.     // freopen("feast.out", "wt", stdout);
  199. #endif
  200.  
  201.     FastIO
  202.     int tc = 1;
  203.     // cin >> tc;
  204.     init_hash();
  205.     while (tc--) {
  206.         solve();
  207.     }
  208.  
  209.  
  210.     return 0;
  211. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000007
https://ideone.com/fgPdq9
language:
C++14 (gcc 8.3)
created:
2 days 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!