Advertisement
Guest User

Untitled

a guest
Nov 21st, 2019
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.34 KB | None | 0 0
  1. #include <iostream>
  2. #include <set>
  3. #include <map>
  4. #include <numeric>
  5. using namespace std;
  6.  
  7. struct fraction {
  8.     int64_t p, q;
  9.     fraction(int64_t _p, int64_t _q) {
  10.         int64_t g = gcd(_p, _q);
  11.         p = _p / g;
  12.         q = _q / g;
  13.     }
  14.  
  15.     bool operator<(const fraction& f) const {
  16.         return p * f.q < q * f.p;
  17.     }
  18. };
  19.  
  20. const int N = 2e5 + 31, VN = 2 * N;
  21.  
  22. char s[N + 1];
  23. map<char, int> t[VN];
  24. int l[VN], r[VN], p[VN];
  25. int n = 0, suf[VN], vn = 2, v = 1, pos = 0;
  26.  
  27. set<int> lens[VN];
  28. fraction ans(1, 1);
  29.  
  30. int dfs(int v, int len) {
  31.     if (t[v].empty()) {
  32.         lens[v].insert(len);
  33.         return N;
  34.     }
  35.     int md = N;
  36.     for (auto [c, u] : t[v]) {
  37.         md = min(md, dfs(u, len + min(n, r[u]) - l[u]));
  38.         if (lens[v].size() < lens[u].size()) {
  39.             lens[v].swap(lens[u]);
  40.         }
  41.         for (int x : lens[u]) {
  42.             auto it = lens[v].lower_bound(x);
  43.             if (it != lens[v].end()) {
  44.                 md = min(md, *it - x);
  45.             }
  46.             if (it != lens[v].begin()) {
  47.                 --it;
  48.                 md = min(md, x - *it);
  49.             }
  50.             lens[v].insert(x);
  51.         }
  52.     }
  53.     if (md != N) {
  54.         ans = max(ans, fraction(len + md, md));
  55.     }
  56.     return md;
  57. }
  58.  
  59. int main() {
  60.     ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  61.  
  62.     string w;
  63.     cin >> w;
  64.     w += '$';
  65.     for (char c = 0; c < 127; c++) {
  66.         t[0][c] = 1;
  67.     }
  68.     l[1] = -1;
  69.  
  70.     for (n = 0; n < int(w.size()); n++) {
  71.         char c = s[n] = w[n];
  72.         auto new_leaf = [&]( int v ) {
  73.             p[vn] = v, l[vn] = n, r[vn] = N, t[v][c] = vn++;
  74.         };
  75.         go:;
  76.         if (r[v] <= pos) {
  77.             if (!t[v].count(c)) {
  78.                 new_leaf(v), v = suf[v], pos = r[v];
  79.                 goto go;
  80.             }
  81.             v = t[v][c], pos = l[v] + 1;
  82.         } else if (c == s[pos]) {
  83.             pos++;
  84.         } else {
  85.             int x = vn++;
  86.             l[x] = l[v], r[x] = pos, l[v] = pos;
  87.             p[x] = p[v], p[v] = x;
  88.             t[p[x]][s[l[x]]] = x, t[x][s[pos]] = v;
  89.             new_leaf(x);
  90.             v = suf[p[x]], pos = l[x];
  91.             while (pos < r[x])
  92.                 v = t[v][s[pos]], pos += r[v] - l[v];
  93.             suf[x] = (pos == r[x] ? v : vn);
  94.             pos = r[v] - (pos - r[x]);
  95.             goto go;
  96.         }
  97.     }
  98.    
  99.     for (auto [c, v] : t[1]) {
  100.         if (c != '$') {
  101.             dfs(v, min(n, r[v]) - l[v]);
  102.         }
  103.     }
  104.  
  105.     cout << ans.p << "/" << ans.q << "\n";
  106.  
  107.     return 0;
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement