题目大意简化

给定一个长度为 n 的 01 字符串 S。

• 每个位置 i 代表一个事件，该事件是字符串的一个前缀 S[1..i]（从1开始索引）。
• 两个事件 i 和 j (假设 i < j) 的“相似度”定义为它们对应前缀的 最长公共后缀 的长度。
• 有 m 个查询，每个查询给出一个区间 [l, r]，要求找出所有在 l 到 r 之间结束的事件中（即 i, j ∈ [l, r] 且 i < j），最大的相似度是多少。

关键思路转换

1. 最长公共后缀 (Longest Common Suffix) 两个前缀 S[1..i] 和 S[1..j] 的最长公共后缀，等价于将整个字符串 S 反转 后，对应的两个后缀 reverse(S)[1..n-i+1] 和 reverse(S)[1..n-j+1] 的 最长公共前缀 (Longest Common Prefix, LCP)。

2. 问题转化 令 S' = reverse(S)。 在原串中，位置 i 和 j 的事件，其相似度等于新串 S' 中后缀 S'[n-i+1..] 和 S'[n-j+1..] 的 LCP 长度。 如果我们定义原串 S 的后缀 i 为 S[i..n]，那么 S' 的后缀 (n-j+1) 其实就是原串后缀 j 的反转。但更直接的理解是： 原串中前缀结束位置 i 和 j 的公共后缀长度，等于原串中后缀 i 和后缀 j 的公共前缀长度。

3. 问题最终形式 经过转换，问题变成了：

   • 有一个字符串 S。
   • 对于查询 [l, r]，我们需要在所有 i, j ∈ [l, r] (i < j) 中，找到 后缀 i 和 后缀 j 的 LCP 的最大值。

标准解法

1. 后缀数组与Height数组

   • 构建 S 的 后缀数组 (SA)，将后缀按字典序排序。
   • 构建 Height数组，Height[i] 表示排名第 i 的后缀与排名第 i-1 的后缀的 LCP 长度。

2. LCP与RMQ的关系

   • 后缀数组有一个关键性质：任意两个后缀 i 和 j（指它们在原串中的起始位置）的 LCP，等于它们在后缀数组中排名之间的 Height 数组的区间最小值。
   • 即 LCP(i, j) = min(Height[rank[i]+1], Height[rank[i]+2], ..., Height[rank[j]]) (假设 rank[i] < rank[j])。

3. 问题再次转化 现在，我们要求解的是：在区间 [l, r] 内，找到两个不同的位置 i, j，使得 LCP(i, j) 最大。 根据上述性质，LCP(i, j) 的大小由它们在后缀数组中排名区间内的最小 Height 值决定。 因此，问题等价于： 在后缀数组中，所有起始位置在 [l, r] 的后缀，我们考虑它们在 SA 中的排名。最大的 LCP 必然出现在 排名相邻 且起始位置都在 [l, r] 内的两个后缀之间。

4. 核心结论

   • 设 [L, R] 是后缀数组中，所有起始位置在 [l, r] 的后缀对应的排名集合。
   • 那么答案就是 max{ min(Height[L+1], Height[L+2], ..., Height[R]) }？不对。
   • 更准确地说： 答案是所有满足 i, j ∈ [l, r] 且在后缀数组中排名相邻的后缀对的 LCP 的最大值。即： [ ans = \max_{k \in [L+1, R]} { Height[k] } ] 因为 Height[k] 本身就是相邻两个后缀的 LCP，而这两个后缀的起始位置如果都在 [l, r] 内，那么它们就是候选解。并且，最大的 LCP 一定出现在排名相邻的两个后缀之间（如果最大的 LCP 出现在不相邻的后缀 a 和 c 之间，那么它们中间的后缀 b 与 a 或 c 的 LCP 至少不会小于 LCP(a, c)，由字典序性质决定）。

5. 算法步骤 a. 构建 S 的后缀数组 SA、排名数组 Rank、高度数组 Height。 b. 预处理 Height 数组的 ST表（Sparse Table），用于 O(1) 查询区间最大值。 c. 对于每个查询 [l, r]：

   • 我们需要找到所有起始位置在 [l, r] 的后缀，它们在后缀数组中的排名集合。
   • 这个排名集合是一个 连续区间 吗？不是，是离散的。
   • 巧妙的方法：我们考虑所有排名相邻且起始位置都在 [l, r] 内的后缀对。这相当于，我们遍历 Height 数组，但只关心那些 SA[i] 和 SA[i-1] 都位于 [l, r] 的 i。如何快速找到这些 i？
   • 实际上，我们可以将问题转化为：对于区间 [l, r]，答案就是 Height 数组中，所有满足 SA[i] 和 SA[i-1] 都在 [l, r] 内的 Height[i] 的最大值。
   • 我们可以预先处理，对于每个位置 i，如果 SA[i] 和 SA[i-1] 都在某个区间，它才贡献答案。但查询时如何快速求最大值？
   • 一个更简洁的实现是：将 (Height[i], min(SA[i], SA[i-1])) 作为候选，但标准做法是使用 线段树 或 单调栈 处理“区间内所有相邻对的最大值”，但这里相邻对是固定的。

   标准且高效的做法（O(n log n) 预处理，O(m) 或 O(m log n) 查询）：

   • 我们意识到，对于固定的 l，当 r 增大时，会有新的后缀加入区间，新的相邻对产生。
   • 我们可以将查询按 r 排序，用并查集或链表维护 Height 数组的相邻关系，用单调栈维护最大值。这就是 离线做法。
   • 或者，我们有一个关键观察：答案就是 [l, r] 区间内，所有后缀在后缀数组中的排名，这些排名构成一个集合，这个集合中相邻排名的 Height 值的最大值。
   • 因此，如果我们能快速得到这个排名集合，并求出其中相邻排名的 Height 最大值，就得到了答案。
   • 而 这个排名集合中的相邻排名，恰好对应了原串 [l, r] 区间内，所有位置在后缀数组中的前驱和后继关系。
   • 所以，我们可以用 链表 或 set 维护当前区间 [l, r] 内所有位置在后缀数组中的排名，并维护相邻排名的 Height 最大值。用 莫队算法 或 离线双指针 来移动区间左右端点，更新答案。

复杂度

• 后缀数组构建：O(n log n) 或 O(n)
• ST表构建：O(n log n)
• 查询处理：
  • 如果使用离线排序 + 链表/Set：O((n+m) log n) 或 O(n α(n) + m log n)
  • 如果使用莫队：O(n √m) 或 O(n log n) （带修改莫队）

在 n, m ≤ 1e5 的数据范围下，O(n log n) 的算法是可行的。

示例代码（C++，基于后缀数组 + RMQ + 离线链表）

// 注意：此为算法框架，省略了后缀数组的具体实现细节
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

// sa: 后缀数组, rk: 排名数组, height: 高度数组
int sa[N], rk[N], height[N];
// 用于离线处理的数据结构
int pre[N], nxt[N], ans[N];
struct Query {
    int l, r, id;
    bool operator<(const Query& other) const {
        return r < other.r; // 按右端点排序
    }
} q[N];

// 并查集或链表维护当前区间内的后缀排名相邻关系
// ... 具体实现较为复杂，此处省略 ...

int main() {
    int n, m;
    string s;
    cin >> n >> m >> s;
    s = " " + s; // 调整为1-indexed

    // 1. 构建后缀数组和Height数组
    build_sa(s, sa, n);     // 实现略
    get_height(s, sa, height, n); // 实现略

    // 2. 读入查询并离线
    for (int i = 1; i <= m; i++) {
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }
    sort(q + 1, q + m + 1);

    // 3. 离线处理查询
    // 使用链表结构，按r递增顺序添加后缀，维护相邻排名的Height最大值
    // ... 具体实现省略 ...

    // 4. 输出答案
    for (int i = 1; i <= m; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}

总结

本题的难点在于 问题转化：

1. 将“前缀的公共后缀”转化为“后缀的公共前缀”。
2. 利用 后缀数组 和 Height数组 的性质。
3. 利用 排名相邻的后缀拥有可能的最大LCP 这一关键结论。
4. 将问题最终转化为 维护区间内相邻排名的Height最大值，并使用 离线算法 或 莫队 高效解决。

掌握了这些字符串问题的经典套路，此类题目便可迎刃而解。