我分析了题目和代码，这是一个关于字符串匹配的问题，需要多次查询字符串 $s$ 的子串与字符串 $t$ 的最长公共子串长度。

题目理解

给定两个只包含字符 $a$ 和 $b$ 的字符串 $s$ 和 $t$，以及 $q$ 次查询。每次查询给出区间 $[l, r]$，需要求出 $s[l \dots r]$ 与 $t$ 的最长公共子串的长度。

代码算法分析

核心思路：后缀数组 + 二分答案

该解决方案使用了一种高效的后缀数组方法：

1. 字符串拼接：将 $s$、分隔符和 $t$ 拼接成新字符串
2. 构建后缀数组：计算拼接后字符串的SA、rank和height数组
3. 预处理ST表：用于快速查询区间最大值
4. 二分答案：对每个查询二分查找可能的最长公共子串长度

关键步骤详解

1. 后缀数组构建

void get_SA() {
    // 使用倍增算法构建后缀数组
    // 初始根据第一个字符排序，然后逐步增加比较长度
}

2. Height数组计算

Height数组存储相邻后缀的最长公共前缀，是算法的核心。

3. 预处理ST表

// 建立ST表用于O(1)查询区间最大值
for (int i = 1; i < lg[la]; ++i) {
    for (int j = 1; j <= la - (1 << i) + 1; ++j) {
        st[j][i] = max(st[j][i - 1], st[j + (1 << i - 1)][i - 1]);
    }
}

4. 二分答案验证

对每个查询 $[l, r]$，二分可能的长度 $mid$：

bool chk(int x) {
    // 检查是否存在长度至少为x的公共子串
    // 使用ST表快速查询区间最大值
}

算法复杂度

• 预处理：$O(n \log n)$ 构建后缀数组和ST表
• 单次查询：$O(\log n)$ 二分答案
• 总复杂度：$O(n \log n + q \log n)$，适合题目数据范围

算法标签

🏷️ 主要算法

后缀数组 - 用于处理字符串匹配和公共子串问题

二分答案 - 对每个查询二分查找最优解

🏷️ 数据结构

ST表 - 稀疏表实现区间最大值查询

字符串拼接 - 将问题转化为单个字符串上的查询

🏷️ 优化技术

倍增算法 - 高效构建后缀数组

高度数组优化 - 利用height数组性质加速计算

🏷️ 问题类型

多模式匹配 - 一个字符串与另一个字符串的多个子串进行匹配

区间查询优化 - 对多个区间查询提供高效解决方案

这个解法充分利用了后缀数组在处理字符串公共子串问题上的优势，通过巧妙的预处理和二分策略，在较大的数据规模下仍能保持高效运行。