题目理解

我们有一个长度为 $n$ 的字符串 $s$，和 $m$ 个查询。每个查询给出四个参数 $a, b, c, d$，要求：

在子串 $s[a \ldots b]$ 的所有子串中，找到与 $s[c \ldots d]$ 的**最长公共前缀（LCP）**的最大值。

形式化描述：

$$\max_{a \leq l \leq r \leq b} \text{LCP}(s[l \ldots r], s[c \ldots d]) $$

问题分析

暴力解法

对于每个查询，枚举 $s[a \ldots b]$ 的所有子串，与 $s[c \ldots d]$ 计算LCP。复杂度为 $O(m \cdot n^3)$，完全不可行。

关键观察

1. LCP与后缀数组：两个字符串的LCP等于它们在后缀数组中对应后缀的LCP
2. 区间子串的LCP：$s[a \ldots b]$ 的所有子串与 $s[c \ldots d]$ 的LCP最大值，实际上是在 $s[a \ldots b]$ 中找一个起始位置，使得从这个位置开始的后缀与 $s[c \ldots d]$ 开头的后缀有最长的LCP

问题转化

设 $T = s[c \ldots d]$，那么问题转化为：

在区间 $[a, b]$ 中找到一个位置 $i$，使得 $\text{LCP}(s[i \ldots n], T)$ 最大，且不超过 $b-i+1$ 和 $d-c+1$。

解法思路

方法：后缀数组 + 二分答案 + 主席树/ST表

算法框架：

1. 预处理：

   • 构建后缀数组 SA 和高度数组 LCP
   • 预处理RMQ用于快速计算两个后缀的LCP
   • 构建主席树维护后缀数组上的位置信息

2. 查询处理：

   • 二分答案 $mid$，判断是否存在 $i \in [a, b]$ 使得 $\text{LCP}(s[i \ldots n], T) \geq mid$
   • 利用后缀数组的性质，找到所有与 $T$ 的LCP $\geq mid$ 的后缀在SA中的区间
   • 用主席树判断该区间内是否存在位置在 $[a, b-mid+1]$ 的后缀

具体步骤

步骤1：构建后缀数组

void build_sa() {
    // 使用倍增法构建后缀数组
    // SA[i]: 排名第i的后缀起始位置
    // Rank[i]: 后缀i的排名
    // Height[i]: SA[i]和SA[i-1]的LCP长度
}

步骤2：预处理RMQ

void build_rmq() {
    // 构建ST表，用于O(1)查询任意两个后缀的LCP
    // lcp(i, j) = min(Height[rank[i]+1], ..., Height[rank[j]])
}

步骤3：二分答案

对于每个查询 $[a, b, c, d]$：

1. 二分答案 $len$，表示可能的LCP长度
2. 检查是否存在 $i \in [a, b-len+1]$ 使得 $\text{LCP}(s[i \ldots n], s[c \ldots n]) \geq len$
3. 利用后缀数组找到所有与后缀 $c$ 的LCP $\geq len$ 的后缀在SA中的区间 $[L, R]$
4. 用主席树检查区间 $[L, R]$ 中是否存在起始位置在 $[a, b-len+1]$ 的后缀

算法复杂度分析

• 后缀数组构建：$O(n \log n)$
• ST表构建：$O(n \log n)$
• 主席树构建：$O(n \log n)$
• 每次查询：$O(\log^2 n)$（二分答案 + 二分区间 + 主席树查询）
• 总复杂度：$O(n \log n + m \log^2 n)$

关键技巧总结

1. 后缀数组：将字符串问题转化为后缀排序问题
2. 二分答案：将最优化问题转化为判定问题
3. RMQ：快速计算任意两个后缀的LCP
4. 主席树：维护后缀数组上的位置信息，支持区间查询
5. 区间二分：在SA上找到所有与目标后缀LCP足够大的后缀

正确性证明

1. 单调性：如果长度为 $len$ 的LCP存在，那么所有更小的长度也存在
2. 完备性：二分答案能够找到最大的可行长度
3. 区间正确性：通过二分在SA上找到的区间确实包含所有与目标后缀LCP足够大的后缀

样例验证

对于样例：

字符串: "aaaaa"
查询1: [1,1]和[1,5] → LCP最大为1
查询2: [1,5]和[1,1] → LCP最大为1  
查询3: [2,3]和[2,3] → LCP最大为2

标签

• 字符串
• 后缀数组
• 二分答案
• 主席树
• RMQ
• 数据结构

这种方法通过结合多种高级数据结构，成功解决了复杂的字符串区间查询问题。