fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <iostream>
  3. #include <utility>
  4. #include <string.h>
  5. #include <string>
  6. #include <math.h>
  7. #include <stack>
  8. #include <set>
  9. #include <map>
  10. #include <queue>
  11. #include <deque>
  12. #include <iterator>
  13. #include <vector>
  14. #include <algorithm>
  15. #include <unordered_map>
  16. #include <bitset>
  17. #include <time.h>
  18. #include <stdlib.h>
  19. #include <numeric>
  20.  
  21. using namespace std;
  22. const long long INF = 1ll << 32;
  23. const double PI = acos(-1);
  24. const int MOD_VAL = 998244353;
  25.  
  26. typedef long long ll;
  27. typedef unsigned long long ull;
  28. typedef long double ld;
  29. typedef vector<int> vi;
  30. typedef vector<ll> vl;
  31. typedef vector<bool> vb;
  32. typedef pair<int, int> pi;
  33. typedef pair<ll, ll> pl;
  34. typedef vector<pi> vpi;
  35. typedef vector<pl> vpl;
  36. typedef vector<vi> vvi;
  37. typedef vector<vb> vvb;
  38. typedef vector<vl> vvl;
  39. typedef vector<vpi> vvpi;
  40. typedef vector<string> vs;
  41. typedef vector <vector<string>> vvs;
  42.  
  43. #define all(v) (v).begin(),(v).end()
  44. #define rall(v) (v).rbegin(),(v).rend()
  45. #define read(v) for (int it = 0; it < v.size(); it++) {scanf("%d", &v[it]);}
  46. #define print(v) for(auto it : v) printf("%d ", (int)it); puts("");
  47. #define readL(v) for (int it = 0; it < v.size(); it++) scanf("%lld", &v[it]);
  48. #define printL(v) for (auto it : v) printf("%lld ", it); puts("");
  49. #define readC(v) for (int it = 0; it < v.size(); it++) {scanf(" %c", &v[it]);}
  50. #define printC(v) for(auto it : v) printf("%c ", it); puts("");
  51. #define IShowSpeed ios::sync_with_stdio(false),cin.tie(nullptr);
  52. #define oo 1000000007
  53.  
  54. void solve() {
  55.     string S;
  56.     cin >> S;
  57.     int N = S.size();
  58.     const ll base1 = 911, mod1 = 1000000007;
  59.     const ll base2 = 3571, mod2 = 1000000009;
  60.     vector<ll> h1(N+1, 0), h2(N+1, 0);
  61.     vector<ll> p1(N+1, 1), p2(N+1, 1);
  62.     for(int i=0;i<N;i++){
  63.         h1[i+1] = (h1[i] * base1 + (S[i]-'a' +1)) % mod1;
  64.         h2[i+1] = (h2[i] * base2 + (S[i]-'a' +1)) % mod2;
  65.         p1[i+1] = p1[i] * base1 % mod1;
  66.         p2[i+1] = p2[i] * base2 % mod2;
  67.     }
  68.     vector<int> ans(N+1, N+1);
  69.     for(int len=1; len<=N; len++){
  70.         vector<pair<ll, int>> lst;
  71.         for(int l=0; l + len <= N; l++) {
  72.             ll ha = (h1[l + len] - h1[l] * p1[len] % mod1 + mod1) % mod1;
  73.             ll hb = (h2[l + len] - h2[l] * p2[len] % mod2 + mod2) % mod2;
  74.             ll key = ha * 1ll * mod2 + hb;
  75.             lst.emplace_back(key, l);
  76.         }
  77.         sort(all(lst));
  78.         for(auto&it:lst)
  79.         cout<<it.first<<" "<<it.second<<endl;
  80.         cout<<endl;
  81.         int m = lst.size();
  82.         int i =0;
  83.         while(i <m){
  84.             ll key = lst[i].first;
  85.             int j =i;
  86.             while(j <m && lst[j].first == key) j++;
  87.             vector<int> ls;
  88.             for(int t=i;t<j;t++) ls.push_back(lst[t].second);
  89.             sort(all(ls));
  90.             int cnt=0, ce=-1;
  91.             for(auto l: ls){
  92.                 int s = l;
  93.                 int e = l + len -2;
  94.                 if(s > ce +1){
  95.                     cnt += (e -s +1);
  96.                     ce = e;
  97.                 }
  98.                 else{
  99.                     if(e > ce){
  100.                         cnt += (e - ce);
  101.                         ce = e;
  102.                     }
  103.                 }
  104.             }
  105.             int k = N - cnt;
  106.             if(k >=1 && k <=N){
  107.                 ans[k] = min(ans[k], len);
  108.             }
  109.             i =j;
  110.         }
  111.     }
  112.     for(int k=1; k<=N; k++) printf("%d ", (ans[k] <=N)? ans[k] :0);
  113.     puts("");
  114. }
  115.  
  116. int main(void) {
  117. #ifndef ONLINE_JUDGE
  118.     freopen("input.txt", "r", stdin);
  119. #endif
  120.     int t =1;
  121.     while(t--)
  122.         solve();
  123.     return 0;
  124. }
  125.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin
copy 
aabcabcaa
stdout
copy 
1000000010 0
1000000010 1
1000000010 4
1000000010 7
1000000010 8
2000000020 2
2000000020 5
3000000030 3
3000000030 6

912000011780 0
912000011780 7
913000011790 1
913000011790 4
1825000023570 2
1825000023570 5
2734000035320 3
2734000035320 6

830834020233120 0
831746020244900 1
831746020244900 4
1662576040477980 2
1662576040477980 5
2490675060675770 6
2490676060675780 3

269005828046425620 3
514606734744796268 5
514606735744796278 2
756889784362305185 0
757720614382538265 1
757720614382538265 4

64304861786402998 3
283468151212751185 4
283468152212751195 1
526582029850493173 0
806728675982335508 2

239481938506992803 1
581727971786723205 3
716221430737408553 0
929811419835717723 2

58189493662741121 2
168042173273726654 1
477712707945001797 0

86416712548273603 1
196269391159259127 0

801412142025146035 0

9 8 4 6 3 4 2 0 1
https://ideone.com/TNki63
language:
C++14 (gcc 8.3)
created:
5 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!