給定一個長度為n的字串，再給定m個詢問，每個詢問包含四個整數l1,r1,l2,r2l1,r1,l2,r2，請你判斷[l1,r1l1,r1]和[l2,r2l2,r2]這兩個區間所包含的字串子串是否完全相同，
字串中只包含大小寫英文字母和數字，
輸入格式
第一行包含整數n和m，表示字串長度和詢問次數，
第二行包含一個長度為n的字串，字串中只包含大小寫英文字母和數字，
接下來m行，每行包含四個整數l1,r1,l2,r2l1,r1,l2,r2，表示一次詢問所涉及的兩個區間，
注意，字串的位置從1開始編號，
輸出格式
對于每個詢問輸出一個結果，如果兩個字串子串完全相同則輸出“Yes”，否則輸出“No”，
每個結果占一行，
資料范圍
1≤n,m≤1051≤n,m≤105
輸入樣例：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
輸出樣例：
Yes
No
Yes
這個題資料小點可以直接substring，但是這個題資料范圍大，字串長度10^5，肯定報錯
思路：
讓字串中的每個字符對應一個數，可以選擇ASCII碼
不能字符對應0，因為A AA 這樣結果都是0，就會造成把不同的字串當成一個字串
eg： A B C D
1 2 3 4 1*p^3+2*p^2+3*p+4 當成了p進制計算
p一般取131或者13331 然后對Q取余 Q一般取2^64
對于一個字串要求[L,R]這個區間的hash值 = h[R]-h[L-1]*p^R-L+1
代碼：#include<iostream> using namespace std; typedef unsigned long long ULL; const int N=100005,P=131; ULL p[N],h[N]; ULL get(int l,int r){ return h[r]-h[l-1]*p[r-l+1]; } int main(){ int n,m; string s; cin>>n>>m>>s; p[0]=1; for(int i=1;i<=n;i++){ p[i]=p[i-1]*P; h[i]=h[i-1]*P+s[i-1]; } 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/98378.html
標籤：其他
上一篇：840. 模擬哈希表（模板）
下一篇：藍橋杯第十屆C組試題C