字符串哈希

题目 字符串哈希

image-0ec34f24

思路分析

image-7e2b1cc1

使用这种方法就假定了人品足够好，不出现冲突

代码实现

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;//越界等同于模2^64
const int N=100010,P=131;//P取131或13331不易碰撞
char str[N];
ULL h[N],p[N];

ULL get(int l,int r)
{
    //1~r减去1~l-1 但是要左移 移多少 r-l+1位 即乘上p^r-l+1
    return h[r]-h[l-1]*p[r-l+1];
}

int main()
{
    int n,m;
    cin>>n>>m;
    cin>>str+1;//不要把某一位映射成P进制0 A如果是0 AA也是0 冲突 所以从1开始

    p[0]=1;//p^0=1
    for(int i=1;i<=n;i++)
    {
        h[i]=h[i-1]*P+str[i];//构造“字符串前缀和” 左移一位加当前位的ascii值（+x*p^0 即x本身）
        p[i]=p[i-1]*P;//等价于p^0 p^1 p^2 p^3
    }

    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;

        if(get(l1,r1)==get(l2,r2))
            puts("Yes");
        else
            puts("No");
    }

    return 0;
}

同类题型

视频讲解

⬅️ 模拟散列表 🏠 00-听课板子