精华内容
下载资源
问答
  • 字符串哈希

    2021-01-07 21:24:11
    何为字符串哈希 所谓字符串哈希,即对一个字符串形成单向加密的过程,使其拥有尽可能独一无二的编号,通过这种低概率的编号重复,使得字符串的匹配尽可能高效。 如何字符串哈希 最普遍的字符串哈希方式,即进制哈希...
  • 字符串哈希:是将字符串的各个字串对应成一个唯一的整数(这一点和普通的哈希不同,字符串哈希不允许哈希),然后在后面的做题中就比较容易,对字符串进行操作了。 给定一个长度为n的字符串,再给定m个询问,每个询问包含...
    字符串哈希:是将字符串的各个字串对应成一个唯一的整数(这一点和普通的哈希不同,字符串哈希不允许哈希),然后在后面的做题中就比较容易,对字符串进行操作了。

    给定一个长度为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
    #include<iostream>
    using namespace std;
    
    typedef unsigned long long ULL; // 字符串哈希设置其对Q取余,设Q=2的64次方,也就是unsigned long long的最大值+1,因为其没有负数,其溢出后又从0开始,所以就省写了取模的代码。
    
    const int N = 100010,P = 131; // P设成131是经验得来的,这样配合Q=2的64次方,不发生冲突的概率在99.99%
    ULL h[N],p[N];  // h[]存放的是从开头开始的各种子串对应的哈希值,p[]存放的是P(131)的各种次方
    
    ULL get_hash(int l,int r){
        return h[r] - h[l - 1]*p[r - l + 1]; 
    }
    
    int main(){
        int n , m;
        char str[100010];
        scanf("%d%d%s",&n,&m,str + 1);
        p[0] = 1;
        
        for (int i = 1; i <= n ; ++i){
            p[i] = p[i-1]*P;
            h[i] = h[i-1]*P + str[i];  // 递推h[i] 
        }
        
        while(m--){
            int l1,r1,l2,r2;
            scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
            if (get_hash(l1,r1) == get_hash(l2,r2)) puts("Yes");  // hash值相同说明字符串相同,因为字符串和hash值是唯一对应的。 
            else puts("No");
        }
        return 0;
    }

     

    展开全文
  • 字符串哈希 0. 前言 Biu 字符串前缀哈希法。预处理出所有字符串前缀的哈希,数组存储,下标从 1 开始存储。 将字符串看成一个 p 进制的数,例如前缀"ABCD"的哈希值:把这个字符串看出 p 进制的数,那么这个值就是:...

    0. 前言

    Biu

    字符串前缀哈希法。预处理出所有字符串前缀的哈希,数组存储,下标从 1 开始存储。

    将字符串看成一个 p 进制的数,例如前缀"ABCD"的哈希值:把这个字符串看出 p 进制的数,那么这个值就是:
    hash[4]=(1p3+2p2+3p1+4p0)%modhash[4] = (1 * p^3 + 2 * p^2 + 3 * p^1 + 4 * p^0 ) \% mod;

    关于 mod 的经验值,131 或者 13331,冲突几率可以忽略不计。

    特殊注意:

    • 不能将某一个字符映射成数字 0,如果一旦 A 映射成了数字 0,那么 AA 也是数字 0,所以映射成从 1 开始
    • 这里的哈希字符串方法是假定不存在冲突的,取上述的模数经验值即可

    这样的哈希方式,配合前缀哈希方式可以求出任意一个子串的哈希值,类似于预处理了前缀和,现求子区间和,公式为:
    h[R]h[L]pR(L1)h[R] - h[L]*p^{R-(L-1)}

    我们可以采用 unsigned long long 的溢出来代替取模 2^64

    1. 字符串哈希

    在这里插入图片描述

    模板:

    #include <iostream>
    
    using namespace std;
    
    typedef unsigned long long ULL;
    
    const int N = 1e5+5, mod = 13331;
    
    int n, m;
    char str[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 >> str + 1;
        
        p[0] = 1;
        for (int i = 1; str[i]; ++i) {
            p[i] = p[i - 1] * mod;    
            h[i] = h[i - 1] * mod + str[i];
        }
        
        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;
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,320
精华内容 7,728
关键字:

字符串哈希