題面
輸入樣例
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
輸出樣例
Yes
No
Yes
題解
- 我們將一個字串看成是一個2進制的數，然后預處理出字串的前綴哈希(這里的哈希值是以前綴為末尾字母為最低位，就比如前綴abc是以c為最低為就是1 * 22 + 2 * 21 + 3 * 20 ),由于哈希值可能較大，我們在實際情況下還會模一個數
- 然后計算區間中兩個字串區間是否相等 ：我們就可以用前綴和公式 h[r] - h[l-1] ,但是我們前面預處理出的是以前綴最低位的哈希值，所以還要給 l 端乘一個 p[r-h+1] 這樣左右兩端的位數就可以相減了，最后算出的哈希值也是以此區間末端位最低為的值（比如2-3區間的bc就是以c為最低為 2 * 21 + 3 * 20 = 7）
- 將字串看成P進制數，P的經驗值是131或13331，取這兩個值的沖突概率低 , 取模的數用264 ,這樣直接用unsigned long long 存盤，溢位的結果就是取模的結果
- 映射的值不能為0 ，因為如果 a 的映射值是0 ，aa的映射值也是0 ，就會發生歧義
- 哈希能解決KMP的大部分問題，哈希在找區間字串相等是O(1)
代碼
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5 + 10;
const int P = 131;
int n, m;
char s[N];
ULL h[N], p[N];
ULL get(int l, int r) {
return h[r] - h[l - 1] * p[r - l + 1];
}
int main() {
cin >> n >> m >> s + 1;
p[0] = 1;
for (int i = 1; i <= n; i++) {
h[i] = h[i - 1] * P + s[i];
p[i] = p[i - 1] * P;
}
while (m--) {
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
if (get(l1, r1) == get(l2, r2)) cout << "Yes" << endl;
else cout << "No" << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/258944.html
標籤：其他