2619. 询问

#include <iostream>
#include <vector>
#include <string>
using namespace std;
using ull = unsigned long long;

const int MAX = 1000010;
ull h[MAX], p[MAX];

bool judge(int m, int x, int len) {
    int l1 = x - m, r1 = l1 + m - 1;
    int l2 = len - m;
    int r2 = len - 1;
    return h[r1 + 1] - h[l1] * p[r1 - l1 + 1] == h[r2 + 1] - h[l2] * p[r2 - l2 + 1];
}

int main() {
    int t{};
    scanf("%d", &t);
    string s;
    for (int i = 0; i < t; i++) {
        cin >> s;
        int len = s.size();
        h[0] = 0;
        p[0] = 1;
        for (int j = 1; j <= s.size(); j++) {
            h[j] = h[j - 1] * 131 + s[j - 1] - 'a' + 1;
            p[j] = p[j - 1] * 131;
        }
        int num{};
        cin >> num;
        int x;
        for (int i = 0; i < num; i++) {
            scanf("%d", &x);
            int l = 0, r = x;
            while (l < r) {
                int m = (l + r + 1) >> 1;
                if (!judge(m, x, len)) r = m - 1;
                else l = m;
            }
            printf("%d\n", l);
        }
    }
}