预处理阶段

1. 后缀自动机（SAM）构建：

   $$O(m)$$

   其中 $m$ 是模式串 $T$ 的长度。

2. 文本串 $S$ 匹配：

   $$O(n)$$

   其中 $n$ 是文本串 $S$ 的长度。

3. 稀疏表（ST表）预处理：

   $$O(n \log n)$$

   其中 $n$ 是文本串 $S$ 的长度。

查询阶段

1. 每组查询的二分时间复杂度：

   $$O(\log n)$$

   其中 $n$ 是文本串 $S$ 的长度。

2. 单次区间最大值查询：

   $$O(1)$$

整体时间复杂度

其中 $m$ 是模式串 $T$ 的长度，$n$ 是文本串 $S$ 的长度，$q$ 是查询次数。

关键验证逻辑

对于二分答案中的长度 $mid$，验证条件为： 存在 $k \in [l + mid - 1, r]$ 使得 $len_S[k] \geq mid$，其中 $len_S[k]$ 表示 $S$ 中以第 $k$ 个字符结尾的子串与 $T$ 的最长公共子串长度。

算法步骤

1. 构建 $T$ 的 SAM：线性时间 $O(m)$
2. 匹配 $S$ 得到 $len_S$ 数组：线性时间 $O(n)$
3. 预处理 $len_S$ 的 ST 表：$O(n \log n)$
4. 处理每组查询：
   • 二分答案：$O(\log n)$
   • 每次验证：$O(1)$（ST 表区间最大值查询）

这种组合解法充分利用了各算法的优势，确保在大数据范围下的高效运行。

AC code：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int MAX_SAM = 4e5 + 5;

struct SAMNode {
    int len, link;
    int next[2];
    SAMNode() { len = 0; link = -1; memset(next, -1, sizeof(next)); }
} sam[MAX_SAM];
int sam_cnt, last;

void sam_init() {
    sam_cnt = 0;
    last = 0;
    sam[0] = SAMNode();
}

void sam_extend(int c) {
    int cur = ++sam_cnt;
    sam[cur].len = sam[last].len + 1;
    int p = last;
    while (p != -1 && sam[p].next[c] == -1) {
        sam[p].next[c] = cur;
        p = sam[p].link;
    }
    if (p == -1) {
        sam[cur].link = 0;
    } else {
        int q = sam[p].next[c];
        if (sam[p].len + 1 == sam[q].len) {
            sam[cur].link = q;
        } else {
            int clone = ++sam_cnt;
            sam[clone].len = sam[p].len + 1;
            memcpy(sam[clone].next, sam[q].next, sizeof(sam[q].next));
            sam[clone].link = sam[q].link;
            while (p != -1 && sam[p].next[c] == q) {
                sam[p].next[c] = clone;
                p = sam[p].link;
            }
            sam[q].link = clone;
            sam[cur].link = clone;
        }
    }
    last = cur;
}

int log_table[MAXN];
int dp[MAXN][20];
int len_S[MAXN];
int n, m, q;
void st_preprocess() {
    log_table[1] = 0;
    for (int i = 2; i <= n; i++) {
        log_table[i] = log_table[i / 2] + 1;
    }
    int k_max = log_table[n] + 1;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = len_S[i];
    }
    for (int j = 1; j < k_max; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            dp[i][j] = max(dp[i][j-1], dp[i + (1 << (j-1))][j-1]);
        }
    }
}

int st_query(int l, int r) {
    if (l > r) return 0;
    int k = log_table[r - l + 1];
    return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}

int main() {
    freopen("seal.in", "r", stdin);
    freopen("seal.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    string S, T;
    cin >> S >> T;
    S = " " + S;
    T = " " + T;
    sam_init();
    for (int i = 1; i <= m; i++) {
        sam_extend(T[i] - '0');
    }
    int cur = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        int c = S[i] - '0';
        while (cur != -1 && sam[cur].next[c] == -1) {
            cur = sam[cur].link;
            if (cur != -1) cnt = sam[cur].len;
            else cnt = 0;
        }
        if (cur == -1) {
            cur = 0;
            cnt = 0;
        } else {
            cur = sam[cur].next[c];
            cnt++;
        }
        len_S[i] = cnt;
    }
    st_preprocess();
    while (q--) {
        int l, r;
        cin >> l >> r;
        int max_L = min(r - l + 1, m);
        int low = 0, high = max_L, ans = 0;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (mid == 0) {
                ans = mid;
                low = mid + 1;
                continue;
            }
            int Lk = l + mid - 1;
            int Rk = r;
            if (Lk > Rk) {
                high = mid - 1;
                continue;
            }
            int max_val = st_query(Lk, Rk);
            if (max_val >= mid) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        cout << ans << endl;
    }

    return 0;
}