编辑代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <unordered_map>

using namespace std;

struct State {
    unordered_map<char, State*> transitions;
    State* suffix_link = nullptr;
    int length = 0;
    int id;
    State(int _id) : id(_id) {}
};

class SuffixAutomaton {
public:
    State* root;
    State* last;
    int size;
    vector<State*> states;

    SuffixAutomaton() {
        size = 0;
        root = new State(size++);
        root->suffix_link = root;
        last = root;
        states.push_back(root);
    }

    void extend(char c) {
        State* curr = new State(size++);
        curr->length = last->length + 1;
        State* p = last;
        while (p->transitions.find(c) == p->transitions.end()) {
            p->transitions[c] = curr;
            p = p->suffix_link;
        }
        State* q = p->transitions[c];
        if (p->length + 1 == q->length) {
            curr->suffix_link = q;
        } else {
            State* clone = new State(size++);
            clone->transitions = q->transitions;
            clone->suffix_link = q->suffix_link;
            clone->length = p->length + 1;
            while (p->transitions[c] == q) {
                p->transitions[c] = clone;
                p = p->suffix_link;
            }
            q->suffix_link = clone;
            curr->suffix_link = clone;
            states.push_back(clone);
        }
        last = curr;
        states.push_back(curr);
    }
};

struct Block {
    vector<int> starts; // 排序后的start_i
    vector<int> lens; // 对应的len_end
    vector<int> max_from_end;
    int max_start; // 块中最大的start_i
    int min_i, max_i; // 块的i范围
    vector<int> original_start; // 按i顺序存储的start_i
    vector<int> original_len;   // 按i顺序存储的len_end
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string s, t;
    cin >> s >> t;
    int n = s.size();
    int m = t.size();
    int q;
    cin >> q;

    SuffixAutomaton sam;
    for (char c : t) {
        sam.extend(c);
    }

    vector<int> len_end(n + 1, 0); // 1-based
    State* current = sam.root;
    int current_len = 0;
    for (int i = 1; i <= n; ++i) {
        char c = s[i - 1];
        while (current != sam.root && current->transitions.find(c) == current->transitions.end()) {
            current = current->suffix_link;
            current_len = current->length;
        }
        if (current->transitions.find(c) != current->transitions.end()) {
            current = current->transitions[c];
            current_len++;
        } else {
            current = sam.root;
            current_len = 0;
        }
        len_end[i] = current_len;
    }

    vector<int> start_i(n + 1);
    for (int i = 1; i <= n; ++i) {
        start_i[i] = i - len_end[i] + 1;
    }

    // 分块处理
    int B = static_cast<int>(sqrt(n)) + 1;
    vector<Block> blocks;
    for (int i = 1; i <= n; i += B) {
        int block_start = i;
        int block_end = min(i + B - 1, n);
        Block blk;
        blk.min_i = block_start;
        blk.max_i = block_end;
        vector<pair<int, int>> temp;
        for (int j = block_start; j <= block_end; ++j) {
            temp.emplace_back(start_i[j], len_end[j]);
            blk.original_start.push_back(start_i[j]);
            blk.original_len.push_back(len_end[j]);
        }
        sort(temp.begin(), temp.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.first < b.first;
        });
        for (auto& p : temp) {
            blk.starts.push_back(p.first);
            blk.lens.push_back(p.second);
        }
        int sz = blk.lens.size();
        blk.max_from_end.resize(sz);
        if (sz > 0) {
            blk.max_start = blk.starts.back();
            blk.max_from_end[sz - 1] = blk.lens[sz - 1];
            for (int j = sz - 2; j >= 0; --j) {
                blk.max_from_end[j] = max(blk.lens[j], blk.max_from_end[j + 1]);
            }
        } else {
            blk.max_start = 0;
        }
        blocks.push_back(blk);
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        int max_len = 0;

        for (const Block& blk : blocks) {
            // 块的i范围与查询区间无交集
            if (blk.max_i < l || blk.min_i > r) continue;
            // 块中最大的start_i都小于l，无需处理
            if (blk.max_start < l) continue;

            if (blk.min_i >= l && blk.max_i <= r) {
                // 整个块在查询区间内
                if (blk.starts.empty()) continue;
                auto it = lower_bound(blk.starts.begin(), blk.starts.end(), l);
                int pos = it - blk.starts.begin();
                if (pos < blk.starts.size()) {
                    max_len = max(max_len, blk.max_from_end[pos]);
                }
            } else {
                // 块部分在查询区间内，检查i在[l..r]内的部分
                int start_in_block = max(blk.min_i, l);
                int end_in_block = min(blk.max_i, r);
                int start_idx = start_in_block - blk.min_i;
                int end_idx = end_in_block - blk.min_i;
                for (int idx = start_idx; idx <= end_idx; ++idx) {
                    if (blk.original_start[idx] >= l) {
                        max_len = max(max_len, blk.original_len[idx]);
                    }
                }
            }
        }

        cout << max_len << '\n';
    }

    return 0;
}