Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // #include <bits\stdc++.h>
- #include <iostream>
- #include <map>
- #include <vector>
- #ifdef LOCAL
- #define dbg(x) cerr << #x << " = " << (x) << endl;
- #else
- #define dbg(x)
- #endif
- #define int long long
- #define endl "\n"
- #define x first
- #define y second
- #define len(x) ((int)(x).size())
- using namespace std;
- void solve(); signed main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- // freopen("loganqueries.in", "r", stdin);
- // freopen("loganqueries.out", "w", stdout);
- #endif
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- cout.setf(ios::fixed); cout.precision(15);
- solve();
- }
- const int INF = 1e18, MAXN = 3e5 + 10, MOD = 1e9 + 7;
- vector<int> lcp;
- vector<int> p, c;
- vector<int> calc_lcp(vector<int> &val, vector<int> &c, vector<int> &p) {
- int n = len(val);
- int current_lcp = 0;
- vector<int> lcp(n);
- for (int i = 0; i < n; i++) {
- if (c[i] == n - 1)
- continue;
- int nxt = p[c[i] + 1];
- while (max(i, nxt) + current_lcp < n && val[i + current_lcp] == val[nxt + current_lcp])
- current_lcp++;
- lcp[c[i]] = current_lcp;
- current_lcp = max(0ll, current_lcp - 1);
- }
- return lcp;
- }
- vector<int> suffix_array(vector<int> &s) {
- s.push_back(0);
- int n = len(s),cnt = 0, cls = 0;
- c.resize(n), p.resize(n);
- map<int, vector<int>> t;
- for (int i = 0; i < n; i++)
- t[s[i]].push_back(i);
- for (auto &x : t) {
- for (int u : x.y)
- c[u] = cls, p[cnt++] = u;
- cls++;
- }
- for (int l = 1; cls < n; l++) {
- vector<vector<int>> a(cls);
- vector<int> _c(n);
- int d = (1 << l) / 2;
- int _cls = cnt = 0;
- for (int i = 0; i < n; i++) {
- int k = (p[i] - d + n) % n;
- a[c[k]].push_back(k);
- }
- for (int i = 0; i < cls; i++) {
- for (int j = 0; j < len(a[i]); j++) {
- if (j == 0 || c[(a[i][j] + d) % n] != c[(a[i][j - 1] + d) % n])
- _cls++;
- _c[a[i][j]] = _cls - 1;
- p[cnt++] = a[i][j];
- }
- }
- c = _c;
- cls = _cls;
- }
- lcp = calc_lcp(s, c, p);
- return vector<int>(p.begin() + 1, p.end());
- }
- void solve() {
- int n, m;
- cin >> n >> m;
- vector<int> a(n);
- for (int i = 0; i < n; ++i) {
- cin >> a[i];
- }
- vector<int> sm = suffix_array(a);
- // for (auto it: lcp) {
- // cerr << it << " ";
- // }
- // cerr << endl;
- vector<int> ind1, ind2;
- vector<int> bl(n, -1), br(n, -1);
- for (int i = 0; i < n + 1; ++i) {
- while (ind1.size() > 0 && lcp[ind1.back()] > lcp[i]) {
- br[ind1.back()] = i;
- ind1.pop_back();
- }
- ind1.push_back(i);
- while (ind2.size() > 0 && lcp[ind2.back()] > lcp[n - i - 1]) {
- bl[ind2.back()] = n - i - 1;
- ind2.pop_back();
- }
- ind2.push_back(n - i - 1);
- }
- int ans = n, id = 0, ll = n;
- for (int i = 1; i < n; ++i) {
- int k = lcp[i];
- int l = bl[i], r = br[i];
- if (l == -1 || r == -1) {
- continue;
- }
- l++;
- // cerr << l << " " << r << " " << k << endl;
- if (ans < (r - l + 1) * k) {
- ans = (r - l + 1) * k;
- id = p[i];
- ll = (r - l + 1);
- }
- }
- cout << ans << endl;
- cout << ll << endl;
- for (int i = id; i < min(n, ll + id); ++i) {
- cout << a[i] << " ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement