【算法】字元串hash

題目描述

很久很久以前，森林裡住着一群兔子。

有一天，兔子們想要研究自己的 DNA 序列。

我們首先選取一個好長好長的 DNA 序列（小兔子是外星生物，DNA 序列可能包含 26 個小寫英文字母）。

然後我們每次選擇兩個區間，詢問如果用兩個區間裡的 DNA 序列分别生産出來兩隻兔子，這兩個兔子是否一模一樣。

注意兩個兔子一模一樣隻可能是他們的 DNA 序列一模一樣。

輸入格式

第一行輸入一個 DNA 字元串 S。

第二行一個數字 m，表示 m 次詢問。

接下來 m 行，每行四個數字 l1,r1,l2,r2l1,r1,l2,r2，分别表示此次詢問的兩個區間，注意字元串的位置從1開始編号。

輸出格式

對于每次詢問，輸出一行表示結果。

如果兩隻兔子完全相同輸出 YesYes，否則輸出 NoNo（注意大小寫）。

資料範圍

1≤length(S),m≤10000001≤length(S),m≤1000000

樣例

輸入樣例：

aabbaabb

3

1 3 5 7

1 3 6 8

1 2 1 2

輸出樣例：

Yes

No

Yes

分析：

字元串哈希，維護哈希字首和，實作線性查詢

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
#define hash 131
#define ull unsigned long long
typedef pair<int,int> PII;
const int N=1e6+7;
ull p[N],sum[N];
int n,m,len,l1,r1,l2,r2;
char s[N];
int main()
{
    scanf("%s",s+1);
    len=strlen(s+1);
    cin>>n;
    p[0]=1;
        for(int i=1;i<=len;i++){
            sum[i]=sum[i-1]*hash+(s[i]-'a'+1);
            p[i]=p[i-1]*hash;
        }
        for(int i=1;i<=n;i++){
            cin>>l1>>r1>>l2>>r2;
            if(sum[r1]-sum[l1-1]*p[r1-l1+1]==sum[r2]-sum[l2-1]*p[r2-l2+1]) cout<<"Yes"<<endl;
                else cout<<"No"<<endl;
        }
}