求字符串某段哈希表

//求字符串某段哈希表

//1、已知h[i] 表示第i个字符化为的数字

//2、求h[i]的同时 再求q[i]

//3、最后有公式： str[l,r] : hash_num=h[r]-h[l-1]*p[r-l+1]

//4、如果字符串相同 则hash_num也会相同

#include <iostream>
#include <cstring>
typedef unsigned long long ULL;
using namespace std;

const int N=1000010,base=131;//字符串长度和固定磅数

char str[N];
ULL h[N],p[N];

int main(){
    scanf("%s",str+1);
    int len=strlen(str+1);

    //定义哈希表
    p[0]=1;
    for(int i=1;i<=len;i++)
    {
        h[i]=h[i-1]*base + str[i]-'a'+1;
        p[i]=p[i-1]*base;
    }

    //测试m个数据
    int m;
    cin>>m;
    while(m--)
    {
        int l,r;
        cin>>l>>r;

        int hash_num=h[r]-h[l-1]*p[r-l+1];
        cout<<hash_num<<endl;
    }

    return 0;
}