task_C.cpp

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <tuple>
#include <map>

using std::string;
using std::vector;
using std::pair;
using std::make_pair;
using std::max;
using std::stack;
using std::tuple;
using std::tie;
using std::map;
using std::get;
using std::cout;
using std::cin;

constexpr int64_t alphabet_len = 256;

auto kasai_lcp(const vector<int64_t>& str, const vector<int64_t>& sufarray) {
    long long n = str.size();
 
    auto W = vector<long long>(n); //W[i] -- позиция суффикса i в суффиксном массиве.
 
    for (long long i = 0; i < n; ++i) {
        W[sufarray[i]] = i;
    }
 
    long long cur_lcp = 0;
    auto lcp = vector<long long>(n);
 
    for (long long i = 0; i < n; ++i ) {
        if (W[i] == n - 1) {
            cur_lcp = 0;
            continue;
        }
 
        long long nxt = sufarray[W[i] + 1];
 
        while (max(i + cur_lcp, nxt + cur_lcp) < n ) {
            if (str[i + cur_lcp] != str[nxt + cur_lcp]) break;
            ++cur_lcp;
        }
 
        lcp[W[i]] = cur_lcp;
 
        if (cur_lcp > 0) --cur_lcp;
    }
 
    return lcp;
}

auto suffix_array(const vector<int64_t>& s) {

    int64_t n = s.size();
 
    auto C = vector<int64_t>(n);
    auto P = vector<int64_t>(n); //Суффикс элемента, находящегося на позиции i.
    auto sorter = vector<int64_t>(std::max(n, alphabet_len) + 1);
 
    for (int64_t i = 0; i < n; ++i) {
        ++sorter[s[i]];
    }
 
    for (int64_t j = 1; j < alphabet_len; ++j) {
        sorter[j] += sorter[j - 1];
    }
 
    for (int64_t i = 0; i < n; ++i) {
        P[--sorter[s[i]]] = i;
    }
 
    C[P[0]] = 0;
 
    int64_t num_classes = 1;
 
    for (int64_t i = 1; i < n; ++i) {
        if (s[P[i]] != s[P[i - 1]]) {
            ++num_classes;
        }
 
        C[P[i]] = num_classes - 1;
    }
 
    for (int64_t k = 0; (1 << k) < n; ++k) {
        auto cur_len = 1 << (k);
        auto sorter = vector<int64_t>(std::max(n, alphabet_len) + 1, 0);
        auto cur_p = vector<int64_t>(n);
 
        for (int64_t i = 0; i < n; ++i) {
            cur_p[i] = (P[i] - cur_len);
            if (cur_p[i] < 0) cur_p[i] += n;
        }
 
        for (int64_t i = 0; i < n; ++i) {
            ++sorter[C[cur_p[i]]];
        }
 
        for (int64_t j = 1; j < num_classes; ++j) {
            sorter[j] += sorter[j - 1];
        }
 
 
        for (int64_t i = n - 1; i >= 0; --i) {
            P[--sorter[C[cur_p[i]]]] = cur_p[i];
        }
 
        auto newC = vector<int64_t>(n);
        newC[P[0]] = 0;
        num_classes = 1;
 
        for (int64_t i = 1; i < n; ++i) {
            auto cur  = make_pair(C[P[i    ]], C[(P[i    ] + cur_len) % n]);
            auto prev = make_pair(C[P[i - 1]], C[(P[i - 1] + cur_len) % n]);
 
            if (cur != prev) {
                ++num_classes;
            }
 
            newC[P[i]] = num_classes - 1;
        }
 
        C.swap(newC);
    }
 
//    P.erase(P.begin());
    return P;

}

auto refrain(const vector<int64_t>& str) {
    
    auto suffarray = suffix_array(str);
    auto lcp = kasai_lcp(str, suffarray);

    auto s = stack<tuple<int64_t, int64_t, int64_t>>(); 
    int64_t max_r = 1;
    int64_t max_l = str.size() - 1;
    int64_t start = 0;

    int64_t id, r, l;

    s.emplace(0, 0, -1);

    for (int64_t i = 0; i < lcp.size(); i++) {
        while (lcp[i] < std::get<2>(s.top())) {
            tie(id, r, l) = s.top();

            if ((i - r) * l > max_r * max_l) {
                max_l = l;
                max_r = i - r;
                start = suffarray[id];
            }

            s.pop();
        }

        s.emplace(i, std::get<0>(s.top()), lcp[i]);
    }

    cout << max_r * max_l << '\n';
    cout << max_l << '\n';

    for (int64_t i = start; i < start + max_l; i++) {
        std::cout << str[i] << ' ';
    }
}


int main(void){
    int64_t n = 0;
    int64_t m = 0;

    cin >> n >> m;
    auto str = vector<int64_t>(n, 0);

    for (size_t i = 0; i < n; ++i) {
        cin >> str[i];
    }

    int64_t len = str.size();
    str.push_back(0);
    

    refrain(str);

    return 0;

}