洛谷U639316 最长子串询问 题解 字符串哈希+二分

题目链接：https://www.luogu.com.cn/problem/U639316

解题思路：

二分，然后通过哈希判断子串是否相等。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const unsigned long long B = 233;
long long fac[maxn] = {1};unsigned long long hsh[maxn];
int n, m, p, q;
char s[maxn];unsigned long long query(int l, int r) {return hsh[r] - hsh[l-1];
}int cal(int p, int q) {int l = 1, r = n - q + 1, z = 0;while (l <= r) {int mid = (l + r) / 2;if (query(p, p+mid-1) * fac[q-p] == query(q, q+mid-1))z = mid, l = mid + 1;elser = mid - 1;}return z;
}int main() {scanf("%d%d%s", &n, &m, s+1);for (int i = 1; i <= n; i++) {fac[i] = fac[i-1] * B;hsh[i] = hsh[i-1] + (s[i] - 'a' + 1) * fac[i];}while (m--) {scanf("%d%d", &p, &q);int ans = cal(p, q);printf("%d\n", ans);}return 0;
}