SHARE
TWEET

Untitled

a guest Jul 18th, 2019 94 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // #include <bits\stdc++.h>
  2. #include <iostream>
  3. #include <map>
  4. #include <vector>
  5.  
  6. #ifdef LOCAL
  7. #define dbg(x) cerr << #x << " = " << (x) << endl;
  8. #else
  9. #define dbg(x)
  10. #endif
  11. #define int long long
  12. #define endl "\n"
  13. #define x first
  14. #define y second
  15. #define len(x) ((int)(x).size())
  16.  
  17. using namespace std;
  18.  
  19. void solve(); signed main() {
  20. #ifdef LOCAL
  21.     freopen("input.txt", "r", stdin);
  22.     freopen("output.txt", "w", stdout);
  23. #else
  24.     // freopen("loganqueries.in", "r", stdin);
  25.     // freopen("loganqueries.out", "w", stdout);
  26. #endif
  27.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  28.     cout.setf(ios::fixed); cout.precision(15);
  29.     solve();
  30. }
  31.  
  32. const int INF = 1e18, MAXN = 3e5 + 10, MOD = 1e9 + 7;
  33. vector<int> lcp;
  34. vector<int> p, c;
  35.  
  36. vector<int> calc_lcp(vector<int> &val, vector<int> &c, vector<int> &p) {
  37.     int n = len(val);
  38.     int current_lcp = 0;
  39.     vector<int> lcp(n);
  40.     for (int i = 0; i < n; i++) {
  41.         if (c[i] == n - 1)
  42.             continue;
  43.         int nxt = p[c[i] + 1];
  44.         while (max(i, nxt) + current_lcp < n && val[i + current_lcp] == val[nxt + current_lcp])
  45.             current_lcp++;
  46.         lcp[c[i]] = current_lcp;
  47.         current_lcp = max(0ll, current_lcp - 1);
  48.     }
  49.     return lcp;
  50. }
  51.  
  52. vector<int> suffix_array(vector<int> &s) {
  53.     s.push_back(0);  
  54.     int n = len(s),cnt = 0, cls = 0;  
  55.     c.resize(n), p.resize(n);
  56.      
  57.     map<int, vector<int>> t;
  58.     for (int i = 0; i < n; i++)
  59.         t[s[i]].push_back(i);
  60.      
  61.     for (auto &x : t) {
  62.         for (int u : x.y)
  63.             c[u] = cls, p[cnt++] = u;
  64.         cls++;
  65.     }
  66.      
  67.     for (int l = 1; cls < n; l++) {
  68.         vector<vector<int>> a(cls);  
  69.         vector<int> _c(n);  
  70.         int d = (1 << l) / 2;
  71.         int _cls = cnt = 0;  
  72.          
  73.         for (int i = 0; i < n; i++) {
  74.             int k = (p[i] - d + n) % n;
  75.             a[c[k]].push_back(k);
  76.         }
  77.          
  78.         for (int i = 0; i < cls; i++) {
  79.             for (int j = 0; j < len(a[i]); j++) {
  80.                 if (j == 0 || c[(a[i][j] + d) % n] != c[(a[i][j - 1] + d) % n])
  81.                     _cls++;
  82.                 _c[a[i][j]] = _cls - 1;
  83.                 p[cnt++] = a[i][j];
  84.             }
  85.         }
  86.          
  87.         c = _c;
  88.         cls = _cls;
  89.     }
  90.      
  91.     lcp = calc_lcp(s, c, p);
  92.     return vector<int>(p.begin() + 1, p.end());
  93. }
  94.  
  95. void solve() {
  96.     int n, m;
  97.     cin >> n >> m;
  98.     vector<int> a(n);
  99.     for (int i = 0; i < n; ++i) {
  100.         cin >> a[i];
  101.     }
  102.  
  103.     vector<int> sm = suffix_array(a);
  104.  
  105.     // for (auto it: lcp) {
  106.     //     cerr << it << " ";
  107.     // }
  108.     // cerr << endl;
  109.  
  110.     vector<int> ind1, ind2;
  111.     vector<int> bl(n, -1), br(n, -1);
  112.     for (int i = 0; i < n + 1; ++i) {
  113.         while (ind1.size() > 0 && lcp[ind1.back()] > lcp[i]) {
  114.             br[ind1.back()] = i;
  115.             ind1.pop_back();
  116.         }
  117.         ind1.push_back(i);
  118.         while (ind2.size() > 0 && lcp[ind2.back()] > lcp[n - i - 1]) {
  119.             bl[ind2.back()] = n - i - 1;
  120.             ind2.pop_back();
  121.         }
  122.         ind2.push_back(n - i - 1);
  123.     }
  124.  
  125.     int ans = n, id = 0, ll = n;
  126.     for (int i = 1; i < n; ++i) {
  127.         int k = lcp[i];
  128.         int l = bl[i], r = br[i];
  129.  
  130.         if (l == -1 || r == -1) {
  131.             continue;
  132.         }
  133.  
  134.         l++;
  135.         // cerr << l << " " << r << " " << k << endl;
  136.  
  137.         if (ans < (r - l + 1) * k) {
  138.             ans = (r - l + 1) * k;
  139.             id = p[i];
  140.             ll = (r - l + 1);
  141.         }
  142.     }
  143.  
  144.     cout << ans << endl;
  145.     cout << ll << endl;
  146.     for (int i = id; i < min(n, ll + id); ++i) {
  147.         cout << a[i] << " ";
  148.     }
  149. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top