思路与算法

将原珠子序列、分隔符0和其逆序拼在一起，建立SA及LCP/RMQ。枚举块长k，每块取正向位置与反向对应位置中后缀排名较小者作为代表。按代表排名排序，相邻代表的LCP至少k时属于同一种项链块，否则计新类。记录最大类别数及所有达到最大值的k。

正确性说明

同一块正反任选的最小字典序长度k串给出唯一等价代表。后缀排名能确定长度k前缀的字典序；前缀相同但后续不同的代表仍用LCP≥k合并，因此没有误拆或哈希碰撞。每个固定k下原序列只取完整块，最后不足k的部分正确舍弃。枚举所有可能k得到全局最大值，块数n/k小于当前最优时，后续更大k也不可能达到最优，可以停止。

复杂度

拼接串长2n+1。预处理O(n log n)时间、O(n log n)空间，包括稀疏表初始化。块总数按调和级数为O(n log n)，逐k排序总时间O(n log²n)，额外代表数组O(n)。n≤20万，实测峰值约39MiB，满足64MiB。

易错点

逆串块起点为2n+1-l-k（均0下标），不能用原串的同一下标。只比较前k个元素，不能直接按完整后缀排名去重。并列最优k全部按递增顺序输出。独立答案直接用整数元组及其反转的较小值放入集合。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Suffix {
    int n;
    vector<int> sa, rank, height, logs;
    vector<vector<int>> st;
    Suffix(const vector<int> &s) : n(s.size()), sa(n), rank(n), height(n), logs(n + 1) {
        int alphabet = max(n, *max_element(s.begin(), s.end()) + 1);
        {
            vector<int> count(alphabet + 1), temp(n), nr(n);
            for (int x : s)
                ++count[x];
            for (int i = 1; i <= alphabet; ++i)
                count[i] += count[i - 1];
            for (int i = n - 1; i >= 0; --i)
                sa[--count[s[i]]] = i;
            int classes = 0;
            for (int i = 0; i < n; ++i) {
                if (i == 0 || s[sa[i]] != s[sa[i - 1]])
                    ++classes;
                rank[sa[i]] = classes - 1;
            }
            for (int k = 1; k < n && classes < n; k *= 2) {
                int at = 0;
                for (int i = max(0, n - k); i < n; ++i)
                    temp[at++] = i;
                for (int x : sa)
                    if (x >= k)
                        temp[at++] = x - k;
                fill(count.begin(), count.begin() + classes, 0);
                for (int x : temp)
                    ++count[rank[x]];
                for (int i = 1; i < classes; ++i)
                    count[i] += count[i - 1];
                for (int i = n - 1; i >= 0; --i) {
                    int x = temp[i];
                    sa[--count[rank[x]]] = x;
                }
                int nc = 0;
                for (int i = 0; i < n; ++i) {
                    int a = sa[i], b = i ? sa[i - 1] : -1;
                    if (i == 0 || rank[a] != rank[b] ||
                        (a + k < n ? rank[a + k] : -1) != (b + k < n ? rank[b + k] : -1))
                        ++nc;
                    nr[a] = nc - 1;
                }
                rank.swap(nr);
                classes = nc;
            }
        }
        int len = 0;
        for (int i = 0; i < n; ++i) {
            int z = rank[i];
            if (z == 0) {
                len = 0;
                continue;
            }
            int j = sa[z - 1];
            while (i + len < n && j + len < n && s[i + len] == s[j + len])
                ++len;
            height[z] = len;
            if (len)
                --len;
        }
        for (int i = 2; i <= n; ++i)
            logs[i] = logs[i / 2] + 1;
        st.push_back(height);
        for (int k = 1; (1 << k) <= n; ++k) {
            int size = n - (1 << k) + 1;
            st.emplace_back(size);
            for (int i = 0; i < size; ++i)
                st[k][i] = min(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);
        }
    }
    int lcp(int a, int b) const {
        if (a == b)
            return n - a;
        int l = rank[a], rr = rank[b];
        if (l > rr)
            swap(l, rr);
        ++l;
        int k = logs[rr - l + 1];
        return min(st[k][l], st[k][rr - (1 << k) + 1]);
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(2 * n + 1);
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    a[n] = 0;
    for (int i = 0; i < n; ++i)
        a[n + 1 + i] = a[n - 1 - i];
    Suffix sf(a);
    int best = 0;
    vector<int> answers;
    for (int k = 1; k <= n; ++k) {
        if (n / k < best)
            break;
        vector<int> pos;
        pos.reserve(n / k);
        for (int l = 0; l + k <= n; l += k) {
            int b = 2 * n + 1 - l - k;
            pos.push_back(sf.rank[l] < sf.rank[b] ? l : b);
        }
        sort(pos.begin(), pos.end(), [&](int x, int y) {
            return sf.rank[x] < sf.rank[y];
        });
        int count = 0, previous = -1;
        for (int x : pos) {
            if (previous < 0 || sf.lcp(previous, x) < k)
                ++count;
            previous = x;
        }
        if (count > best) {
            best = count;
            answers.clear();
        }
        if (count == best)
            answers.push_back(k);
    }
    cout << best << ' ' << answers.size() << '\n';
    for (size_t i = 0; i < answers.size(); ++i)
        cout << answers[i] << (i + 1 == answers.size() ? '\n' : ' ');
}