字符串哈希 + 二分
题目
你有两个由小写字母组成的字符串 $s_1$ 和 $s_2$,你要比较两个串的某一个子串的字典序大小。
样例:
第一行输入三个整数 $n,m,q$ ,$(1≤n,m,q≤2⋅10^5$)$(1 \leq n,m,q \leq 2 \cdot 10^5)(1≤n,m,q≤2⋅10^5)$分别表示$s_1$的长度、$s_2$的长度和询问的个数
第二行第三行分别是由小写字母组成的字符串$s_1$和 $s_2$
之后 $q$ 行每行四个整数表示$l_1,r_1,l_2,r_2 (1≤l1≤r1≤n,1≤l2≤r2≤m)(1 \leq l_1 \leq r_1 \leq n, 1 \leq l_2 \leq r_2 \leq m)(1≤l1≤r1≤n,1≤l2≤r2≤m)$ 表示 $s_1$ 的子串区间 $[l_1,r_1]$ 和 $s_2 $的子串区间 $[l_2,r_2]$ 。
保证两个子串的长度相同。
输出描述:
对于每个询问,输出一个比较结果 $ans \in \{<,=,>\},$表示比较结果。
思路
- 加快匹配速度,选择字符串哈希。
- 然后对于一个不相等的字符串,它满足一个可二分的性质,如果 长度为 $len$ 的子串是相等的那么就代表长度小于$len$ 的所有子串都是相等的,所以可以二分(以子串的长度二分)找出第一个不相等的地方然后比较
哈希思路
- 可以将字符串看成一个$k$ 进制数,k 可以取$131,233$ 等数,这样可以大致保证每一个字符串的哈希值都不相同。
- 由于字符串的哈希值可能过大,所以我们选择对哈希值取模$998244343$然后得到哈希值。
- 然后对于子串的处理,我们选择类似于前缀和的做法,我们先预处理出所有前缀字符串的哈希值, 然后对于一个$(l , r)$ ,区间的字符串我们就可以用
g[r] - g[l - 1] * h[r - l + 1] % mod
h[]数组则是预处理了进位方便左移操作————假设$ABCDEFG$ 中我们要得到$DEFG$ 我们需要用 $ABCDEFG - ABC0000$ 来得到$DEFG$ 所以我们需要将后一个字符串 移动到前一个字符串同一个数量级。
代码
// Problem: 字串比较
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/76681/I
// Memory Limit: 1048576 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;
const int N = 2e5 + 10;
const int mod = 998244353;
#define int long long
int p[N];
int base = 131;
int ha1[N], ha2[N];
int que(int l, int r, int h[]) {
return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod;
}
void solve() {
int n, m, q;
cin >> n >> m >> q;
p[0] = 1;
string a, b;
cin >> a >> b;
for (int i = 1; i <= 200000; i++) p[i] = p[i - 1] * base % mod;
for (int i = 1; i <= n; i++)
ha1[i] = (ha1[i - 1] * base % mod + a[i - 1]) % mod;
for (int i = 1; i <= m; i++)
ha2[i] = (ha2[i - 1] * base % mod + b[i - 1]) % mod;
while (q--) {
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
int l = 0, r = r1 - l1 + 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (que(l1, l1 + mid - 1, ha1) == que(l2, l2 + mid - 1, ha2))
l = mid;
else
r = mid - 1;
}
if (l == r1 - l1 + 1)
puts("=");
else if (a[l1 + l - 1] < b[l2 + l - 1])
puts("<");
else
puts(">");
}
}
#undef int
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/205739/
强者%%%