fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template<typename X, typename Y>
  5. bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
  6.  
  7. template<typename X, typename Y>
  8. bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }
  9.  
  10. using ll = long long;
  11.  
  12. const int N = 1e5+5;
  13.  
  14. int n;
  15.  
  16. struct State {
  17.     int len, link;
  18.     map<int, int> next;
  19. } sam[2 * N];
  20.  
  21. int sz, last;
  22. int cnt[2 * N], pos[2 * N];
  23.  
  24. void init() {
  25.     sam[0].len = 0;
  26.     sam[0].link = -1;
  27.     sz = 1; last = 0;
  28. }
  29.  
  30. void extend(int c, int idx) {
  31.     int u = sz++;
  32.     sam[u].len = sam[last].len + 1;
  33.     cnt[u] = 1; pos[u] = idx;
  34.     int p = last;
  35.     while (p != -1 && !sam[p].next.count(c)) {
  36.         sam[p].next[c] = u;
  37.         p = sam[p].link;
  38.     }
  39.     if (p == -1) sam[u].link = 0;
  40.     else {
  41.         int q = sam[p].next[c];
  42.         if (sam[p].len + 1 == sam[q].len) sam[u].link = q;
  43.         else {
  44.             int v = sz++;
  45.             sam[v].len = sam[p].len + 1;
  46.             sam[v].link = sam[q].link;
  47.             sam[v].next = sam[q].next;
  48.             cnt[v] = pos[v] = 0;
  49.             while (p != -1 && sam[p].next[c] == q) {
  50.                 sam[p].next[c] = v;
  51.                 p = sam[p].link;
  52.             }
  53.             sam[q].link = sam[u].link = v;
  54.         }
  55.     }
  56.     last = u;
  57. }
  58.  
  59. void solve() {
  60.     cin >> n;
  61.     init();
  62.     for (int i = 1; i <= n; i++) {
  63.         int x; cin >> x;
  64.         extend(x, i);
  65.     }
  66.     vector<int> order(sz);
  67.     for (int i = 0; i < sz; i++) order[i] = i;
  68.     sort(order.begin(), order.end(), [](int x, int y) {
  69.         return sam[x].len > sam[y].len;
  70.     });
  71.     for (int u : order) {
  72.         int p = sam[u].link;
  73.         if (p != -1) {
  74.             cnt[p] += cnt[u];
  75.             chmax(pos[p], pos[u]);
  76.         }
  77.     }
  78.     int best_freq = 0, best_len = 0, best_pos = -1;
  79.     for (int i = 1; i < sz; i++) {
  80.         int f = cnt[i], l = sam[i].len, p = pos[i];
  81.         if (chmax(best_freq, f)) best_len = l, best_pos = p;
  82.         else if (best_freq == f) {
  83.             if (chmax(best_len, l)) best_pos = p;
  84.             else if (best_len == l) chmax(best_pos, p);
  85.         }
  86.     }
  87.     cout << best_pos - best_len + 1 << ' ' << best_pos << '\n';
  88. }
  89.  
  90. int main() {
  91.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  92.  
  93.     #define TASK "BAI4"
  94.     if (fopen(TASK".INP", "r")) {
  95.         freopen(TASK".INP", "r", stdin);
  96.         freopen(TASK".OUT", "w", stdout);
  97.     }
  98.  
  99.     int tests = 1; // cin >> tests;
  100.     while (tests--) solve();
  101.  
  102.     #ifdef LOCAL
  103.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  104.     #endif
  105.     return 0;
  106. }
Success #stdin #stdout 0.01s 14552KB
comments (?)
stdin
copy 
12
3 0 4 1 9 7 5 4 1 9 7 5
stdout
copy 
8 12
https://ideone.com/7cwUdH
language:
C++14 (gcc 8.3)
created:
3 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!