# 字符串哈希 ------------------ [原题链接](https://ac.nowcoder.com/acm/contest/76681/I) ## 题目 > 你有两个由小写字母组成的字符串 $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$ 所以我们需要将后一个字符串 移动到前一个字符串同一个数量级。 ### 代码 ```c++ // 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; } ```