首页 > 其他分享 >字符串哈希/双哈希模板

字符串哈希/双哈希模板

时间:2024-07-25 20:09:00浏览次数:11  
标签:MOD1 MOD2 return get int i64 哈希 字符串 模板

struct Hash {
    using u64 = unsigned long long;
    u64 base = 13331;
    vector<u64> pow, hash;
    Hash(string &s) {
        s = " " + s;
        int N = s.size();
        pow.resize(N + 1), hash.resize(N + 1);
        pow[0] = 1, hash[0] = 0;
        for (int i = 1; i < s.size(); i ++) {
            pow[i] = pow[i - 1] * base;
            hash[i] = hash[i - 1] * base + s[i];
        }
    }

    u64 get(int l, int r) {
        return hash[r] - hash[l - 1] * pow[r - l + 1];
    }

    //拼接两个子串
    u64 link(int l1, int r1, int l2, int r2) {
        return get(l1, r1) * pow[r2 - l2 + 1] + get(l2, r2);
    }

    bool same(int l1, int r1, int l2, int r2) {
        return get(l1, r1) == get(l2, r2);
    }

};
struct DoubleHash {
    const int n;
    const i64 Base1 = 29, MOD1 = 1e9 + 7;
    const i64 Base2 = 131, MOD2 = 1e9 + 9;
    vector<i64> ha1, ha2, pow1, pow2;
    vector<i64> rha1, rha2;
    DoubleHash(string &s, int n1) : n(n1), ha1(n + 1), ha2(n + 1), pow1(n + 1), pow2(n + 1), rha1(n + 1), rha2(n + 1) {
        pow1[0] = pow2[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow1[i] = pow1[i - 1] * Base1 % MOD1;
            pow2[i] = pow2[i - 1] * Base2 % MOD2;
        }
        for (int i = 1; i <= n; i++) {
            ha1[i] = (ha1[i - 1] * Base1 + s[i]) % MOD1;
            ha2[i] = (ha2[i - 1] * Base2 + s[i]) % MOD2;
            rha1[i] = (rha1[i - 1] * Base1 + s[n - i + 1]) % MOD1;
            rha2[i] = (rha2[i - 1] * Base2 + s[n - i + 1]) % MOD2;
        }
    }
    pair<i64, i64> get(int l, int r) {
        i64 res1 = ((ha1[r] - ha1[l - 1] * pow1[r - l + 1]) % MOD1 + MOD1) % MOD1;
        i64 res2 = ((ha2[r] - ha2[l - 1] * pow2[r - l + 1]) % MOD2 + MOD2) % MOD2;
        return {res1, res2};
    }
    //反哈希
    pair<i64, i64> get_rhash(int l, int r) {
        i64 res1 = ((rha1[n - l + 1] - rha1[n - r] * pow1[r - l + 1]) % MOD1 + MOD1) % MOD1;
        i64 res2 = ((rha2[n - l + 1] - rha2[n - r] * pow2[r - l + 1]) % MOD2 + MOD2) % MOD2;
        return {res1, res2};
    }
    //判断s[l, r]是否为回文串
    bool is_palindrome(int l, int r) {
        return get(l, r) == get_rhash(l, r);
    }
    pair<i64, i64> add(pair<i64, i64> aa, pair<i64, i64> bb) {
        i64 res1 = (aa.first + bb.first) % MOD1;
        i64 res2 = (aa.second + bb.second) % MOD2;
        return {res1, res2};
    }
    //aa *= Base的k次方
    pair<i64, i64> mul(pair<i64, i64> aa, i64 kk) {
        i64 res1 = aa.first * pow1[kk] % MOD1;
        i64 res2 = aa.second * pow2[kk] % MOD2;
        return {res1, res2};
    }
    //拼接字符串 r1 < l2  s = s1 + s2
    pair<i64, i64> link(int l1, int r1, int l2, int r2) {
        return add(mul(get(l2, r2), r1 - l1 + 1), get(l1, r1));
    }
};

标签:MOD1,MOD2,return,get,int,i64,哈希,字符串,模板
From: https://www.cnblogs.com/Kescholar/p/18324041

相关文章

  • 字符串探索篇
    leetcode151——反转字符串中的单词题目描述:给你一个字符串 s ,请你反转字符串中 单词 的顺序。单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。注意:输入字符......
  • 第九天|字符串| 151.翻转字符串里的单词,卡码网:55.右旋转字符串,28. 实现 strStr(),459.
    边写边更中Day9花了我好长时间,由于一道题有好几种方法,感觉今天上午下午都在做Day9,心态有点崩,因为今天还没有时间科研。我决定休息一下,先更到这里。气死我了151.翻转字符串里的单词方法1_fff:定义一个新的字符串str,遍历s,从后往前找到每个单词添加到str中classSolu......
  • 设计模式C++001__模板方法
    设计模式C++001__模板方法“组件协作”模式:现代软件专业分工之后的第一个结果就是“框架与应用程序的划分”,组件“协作”模式通过晚绑定,来实现框架与应用程序之间的松耦合。包括:模版方法,观察者模式,策略模式1、模板方法模式:动机:在软件构建过程中,对于一项任务,它常常有稳定的整......
  • C语言:字符串函数、内存函数剖析
    字符串函数、内存函数剖析一、字符串函数(一)求字符串长度1、strlen(1)库函数实现(2)自定义实现(二)长度不受限制的字符串函数1、strcpy(1)库函数实现(2)自定义实现2、strcat(1)库函数实现(2)自定义实现3、strcmp(1)库函数实现(2)自定义实现(三)长度受限制的字符串函数介绍1、strncpy2、s......
  • 字符串哈希
    首先对于知识点会在8月份更新,目前只是单纯的对一道题进行展示题目链接https://ac.nowcoder.com/acm/contest/87255/E题意:题目要求我们找出两个等长的字符串a和b中的“好”字符数量。一个字符被称为“好”字符,如果它在字符串a和b的所有循环同构字符串中出现的位置......
  • C++| STL之unordered_map(哈希表)和map
    前言:Leetcode题目中有一个哈希表的专题,自己实现的话没必要,可以直接用STL现成的unordered_map函数,提到unordered_map就不得不提到map,于是有了此篇相关知识点的汇总。unordered_map和mapkey和valueunordered_map使用map原理对比unordered_map使用对比unordered_mapke......
  • 织梦dedecms模板文件在哪
    首页模板\templets\default\index.htm文章频道首页\templets\default\index_article.htm文章列表页\templets\default\list_article.htm文章内容页\templets\default\article_article.htm图集频道首页\templets\default\index_image.htm图集列表页\templets\defau......
  • 存在重复元素 II-哈希表
    题目描述:个人题解:从左到右遍历数组nums,当遍历到下标i时,如果存在下标j<i使得nums[i]=nums[j],则当i−j≤k时即找到了两个符合要求的下标j和i。如果在下标i之前存在多个元素都和nums[i]相等,为了判断是否存在满足nums[i]=nums[j]且i−j≤k的下标j,应该在这......
  • 代码随想录 day8|| 151 翻转单词 28 字符串匹配 459 重复子串
    151翻转单词funcreverseWords(sstring)string{ //思考:判断单词条件是从0或者空格开始到终或者空格结尾,最简单方式strings.split之后变成切片,然后反转就行了 //考虑双指针,左指针指向单词首位,右指针指向单词末尾 varres[]byte varleft,rightint forright<len......
  • C++模板初探究
    引言        我们如果想要实现一个通用的交换函数,其中包含字符型,整型,双浮点型,该怎么办呢?我们当然可以选择使用函数重载,像这样:voidSwap(int&left,int&right){inttemp=left;left=right;right=temp;}voidSwap(double&left,double&rig......