首页 > 其他分享 >字符串哈希

字符串哈希

时间：2024-10-15 17:35:25浏览次数：6  
标签：hash int pow ++ base l2 哈希 字符串

字符串哈希

哈希函数的基本性质：

1）输入参数的可能性是无限的，输出的值范围相对有限

2）输入同样的样本一定得到同样的输出值，也就是哈希函数没有任何随机机制

3）输入不同的样本也可能得到同样的输出值，此时叫哈希碰撞

4）输入大量不同的样本，得到的大量输出值，会几乎均匀的分布在整个输出域上

  • base 可以选择一些质数比如：433、499、599、1000000007，也可以选择已经被证实了很好用的值：31、131、1313、13131、131313 等。

  • 转化时让每一位的值从1开始，不从0开始。

如何快速得到字符串中任意子串的哈希值：

1）选择一个质数做进制数，base

2）得到 base 的各种次方，在自然溢出下的结果，用 pow 数组记录

3）得到每个位置的 hash[i]，hash[i] = hash[i-1] * base + s[i] - 'a' + 1

4）子串 s[l...r] 的哈希值 = hash[r] - hash[l-1] * base 的 (r-l+1) 次方

P3370 【模板】字符串哈希

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>

using namespace std;

int base = 499;

// 数字 + 大写 + 小写
// [0, 9] 映射成 1~10
// [A, Z] 映射成 11~36
// [a, z] 映射成 37~62
long v(char ch) {
    if (ch >= '0' && ch <= '9') {
        return ch - '0' + 1;
    } else if (ch >= 'A' && ch <= 'Z') {
        return ch - 'A' + 11;
    } else {
        return ch - 'a' + 37;
    }
}

// 计算哈希值：字符串按照 base 进制转换成数字
long value(string s) {
    long res = 0;
    for (int i = 0; i < s.length(); ++i)
        res = res * base + v(s[i]);
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<long> nums(n);
    string str;
    // 计算哈希值后存入数组
    for (int i = 0; i < n; ++i) {
        cin >> str;
        nums[i] = value(str);
    }
    // 统计不同数字的种数
    sort(nums.begin(), nums.end());
    int res = 1;
    for (int i = 1; i < n; ++i)
        if (nums[i] != nums[i - 1]) res++;
    cout << res;
}

独特子串的数量

给你一个由数字组成的字符串 s，返回 s 中独特子字符串数量，其中的每一个数字出现的频率都相同

#include <vector>
#include <iostream>
#include <unordered_set>

using namespace std;

int equalDigitFrequency(string str) {
    int n = str.length();
    long base = 499;
    // 存放字符串的哈希值
    unordered_set<long> st;
    // 记录字符出现频率
    vector<int> freq(10);
    for (int i = 0; i < n; i++) {
        // 重置
        freq.clear();
        freq.resize(10, 0);

        long hashCode = 0;
        // 最大出现次数
        int maxCnt = 0;
        // 最大出现次数的字符种数
        int maxCntKinds = 0;
        // 字符种数
        int allKinds = 0;
        for (int j = i; j < n; j++) {
            int cur = str[j] - '0';
            // 从 1 开始：cur + 1；而不是从零开始：cur
            hashCode = hashCode * base + cur + 1;
            freq[cur]++;
            // 新增一种字符
            if (freq[cur] == 1) allKinds++;
            if (freq[cur] > maxCnt) {
                // 出现频率更大的字符
                maxCnt = freq[cur];
                maxCntKinds = 1;
            } else if (freq[cur] == maxCnt) {
                maxCntKinds++;
            }

            if (maxCntKinds == allKinds) st.emplace(hashCode);
        }
    }
    return st.size();
}

28. 找出字符串中第一个匹配项的下标

#include <vector>
#include <iostream>

using namespace std;

#define ull unsigned long long

class Solution {
public:
    int MAXN = 100005;
    int base = 499;

    vector<ull> pow;
    vector<ull> hash;

    void build(string s, int n) {
        pow.resize(MAXN);
        pow[0] = 1;
        for (int i = 1; i < n; i++)
            pow[i] = pow[i - 1] * base;

        hash.resize(MAXN);
        hash[0] = s[0] - 'a' + 1;
        for (int i = 1; i < n; i++)
            hash[i] = hash[i - 1] * base + s[i] - 'a' + 1;
    }

    // 返回 s[l, r] 的哈希值
    ull hashCode(int l, int r) {
        return l > 0 ? (hash[r] - hash[l - 1] * pow[r - l + 1]) : hash[r];
    }

    int strStr(string haystack, string needle) {
        int n = haystack.length();
        int m = needle.length();

        build(haystack, n);

        ull target = needle[0] - 'a' + 1;
        for (int i = 1; i < m; i++)
            target = target * base + needle[i] - 'a' + 1;

        for (int l = 0, r = m - 1; r < n; l++, r++)
            if (hashCode(l, r) == target)
                return l;
        return -1;
    }
};

686. 重复叠加字符串匹配

#include <vector>
#include <iostream>

using namespace std;

#define ull unsigned long long

class Solution {
public:
    int MAXN = 30001;
    int base = 499;
    vector<ull> pow;
    vector<ull> hash;

    void build(string s) {
        int n = s.length();
        pow.resize(MAXN);
        pow[0] = 1;
        for (int i = 1; i < n; ++i)
            pow[i] = pow[i - 1] * base;

        hash.resize(MAXN);
        hash[0] = s[0] - 'a' + 1;
        for (int i = 1; i < n; ++i)
            hash[i] = hash[i - 1] * base + s[i] - 'a' + 1;
    }

    ull hashCode(int l, int r) {
        return l > 0 ? hash[r] - hash[l - 1] * pow[r - l + 1] : hash[r];
    }

    int repeatedStringMatch(string a, string b) {
        int n = a.length();
        int m = b.length();
        // m / n 向上取整
        int k = (m + n - 1) / n;
        string str = "";
        // a 重复 k + 1 次
        for (int i = 0; i <= k; ++i)
            str.append(a);
        // 计算目标字符串的哈希值
        ull target = b[0] - 'a' + 1;
        for (int i = 1; i < m; ++i)
            target = target * base + b[i] - 'a' + 1;

        build(str);

        for (int i = 0; i < n * k; ++i)
            if (hashCode(i, i + m - 1) == target)
                // 判断最有一个字符有没有到最后一个 a 上
                return i + m - 1 >= n * k ? k + 1 : k;
        return -1;
    }
};

30. 串联所有单词的子串

#include <vector>
#include <iostream>
#include <unordered_map>

using namespace std;

#define ull unsigned long long

class Solution {
public:
    int base = 499;
    vector<ull> pow;
    vector<ull> hash;

    void build(string s) {
        int n = s.length();
        pow.resize(n);
        pow[0] = 1;
        for (int i = 1; i < n; ++i)
            pow[i] = pow[i - 1] * base;

        hash.resize(n);
        hash[0] = s[0] - 'a' + 1;
        for (int i = 1; i < n; ++i)
            hash[i] = hash[i - 1] * base + s[i] - 'a' + 1;
    }

    // 范围是 s[l, r]
    ull hashCode(int l, int r) {
        return l > 0 ? hash[r] - hash[l - 1] * pow[r - l + 1] : hash[r];
    }

    // 计算一个字符串的哈希值
    ull hashCode(string s) {
        if (s == "") return 0;
        int n = s.length();
        ull res = s[0] - 'a' + 1;
        for (int i = 1; i < n; ++i)
            res = res * base + s[i] - 'a' + 1;
        return res;
    }

    // 如果 s 的长度为 n，words 里所有单词的总长度为 m
	// 时间复杂度 O(n + m)
    vector<int> findSubstring(string s, vector<string> &words) {
        vector<int> res;
        if (s == "" || s.length() == 0 || words.size() == 0) return res;

        build(s);
        int n = s.length();
        // 单词长度
        int wordLen = words[0].length();
        // 单词总数
        int wordCount = words.size();
        // 字符总数
        int allLen = wordLen * wordCount;
        // words 的词频表
        unordered_map<ull, int> wordsFreq;
        for (string word: words)
            wordsFreq[hashCode(word)]++;
        // 窗口的词频表
        unordered_map<ull, int> windowFreq;

        // 分为 wordLen 组，init 是当前组的首个开头
        for (int init = 0; init < wordLen && init + allLen <= n; init++) {
            // 缺少的单词总数
            int debt = wordCount;
            // 建立长度为 wordCount 的窗口
            for (int l = init, part = 0; part < wordCount; l += wordLen, part++) {
                // 窗口中每个单词长度都是 wordLen
                ull curHashCode = hashCode(l, l + wordLen - 1);
                windowFreq[curHashCode]++;
                if (windowFreq[curHashCode] <= wordsFreq[curHashCode]) debt--;
            }
            if (debt == 0) res.emplace_back(init);
            // 滑动窗口
            for (int firstLeft = init, lastLeft = init + allLen;
                 lastLeft + wordLen - 1 < n; firstLeft += wordLen, lastLeft += wordLen) {
                ull out = hashCode(firstLeft, firstLeft + wordLen - 1);
                ull in = hashCode(lastLeft, lastLeft + wordLen - 1);
                windowFreq[out]--;
                if (windowFreq[out] < wordsFreq[out]) debt++;
                windowFreq[in]++;
                if (windowFreq[in] <= wordsFreq[in]) debt--;
                // 每次滑动后，都判断是否已经出现所有的单词
                if (debt == 0) res.emplace_back(firstLeft + wordLen);
            }
            windowFreq.clear();
        }
        return res;
    }
};

P3763 [TJOI2017] DNA

根据匹配定义求匹配子串的数量: 给定长为 n 的字符串 s，以及长度为 m 的字符串 p，还有一个正数 k。s' 与 s 匹配的定义为，s' 与 s 长度相同，且最多有 k 个位置字符不同，要求查找字符串 s 中有多少子串与字符串 p 匹配

#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define ull unsigned long long

const int MAXN = 100001;
const int base = 499;

vector<ull> pow;
vector<ull> sHash;
vector<ull> pHash;

void buildPow() {
    pow.resize(MAXN);
    pow[0] = 1;
    for (int i = 1; i < MAXN; ++i)
        pow[i] = pow[i - 1] * base;

    sHash.resize(MAXN);
    pHash.resize(MAXN);
}

// 构建辅助数组
void buildHash(string &s, string &p) {
    sHash[0] = s[0] - 'a' + 1;
    for (int i = 1; i < s.length(); ++i)
        sHash[i] = sHash[i - 1] * base + s[i] - 'a' + 1;
    pHash[0] = p[0] - 'a' + 1;
    for (int i = 1; i < p.length(); ++i)
        pHash[i] = pHash[i - 1] * base + p[i] - 'a' + 1;
}

// 计算子串 [l, r] 的哈希值
ull hashCode(vector<ull> &hash, int l, int r) {
    return l > 0 ? hash[r] - hash[l - 1] * pow[r - l + 1] : hash[r];
}

// 判断长度相同的子串 s[l1, r1] 和 p[l2, r2] 上是否有不同
bool same(int l1, int r1, int l2, int r2) {
    return hashCode(sHash, l1, r1) == hashCode(pHash, l2, r2);
}

// 判断 s[left, left + m -1] 和 p 不同的位置个数是不是小于等于 k
bool smallerK(int left, int m, int k) {
    int diff = 0;
    int l1 = left;
    int r1 = left + m - 1;
    int mid1;
    int end1 = r1;
    int l2 = 0;
    int r2 = m - 1;
    int mid2;
    int end2 = r2;

    while (l2 <= r2 && diff <= k) {
        while (l2 <= r2) {
            mid1 = l1 + ((r1 - l1) >> 1);
            mid2 = l2 + ((r2 - l2) >> 1);
            if (same(l1, mid1, l2, mid2)) {
                // s[l1, mid1] 和 p[l2, mid2] 相同，就在右侧尝试找第一个不同的位置
                l1 = mid1 + 1;
                l2 = mid2 + 1;
            } else {
                // s[l1, mid1] 和 p[l2, mid2] 不同，就在左侧找第一个不同的位置
                r1 = mid1 - 1;
                r2 = mid2 - 1;
            }
        }
        // 结束时 l2 = r2 + 1，l2 左边都是相等的，如果 l2 为 m 说明没有不同的位置了
        if (l2 == m) break;
        // 找到了第一个不同的位置，且位置是 l1,l2
        diff++;
        // 就在右侧区域 [l1 + 1, end1] 和 [l2 + 1, end2] 找第二个不同的位置
        l1++;
        l2++;
        r1 = end1;
        r2 = end2;
    }
    return diff <= k;
}

int solution(string &s, string &p, int k) {
    int n = s.length();
    int m = p.length();
    if (n < m) return 0;
    buildHash(s, p);
    int res = 0;
    for (int i = 0; i <= n - m; i++)
        if (smallerK(i, m, k))
            res++;
    return res;
}

int main() {
    int n;
    cin >> n;
    buildPow();
    for (int i = 0; i < n; ++i) {
        string s, p;
        cin >> s >> p;
        cout << solution(s, p, 3) << endl;
    }
}

标签：hash,int,pow,++,base,l2,哈希,字符串
From： https://www.cnblogs.com/sprinining/p/18468030

相关文章

  • 例2.11_2首先生成包含1000个随机字符的字符串，然后统计每个字符的出现次数，注意get()方
    #利用collections模块的Counter()函数直接作出统计 #依次加载三个模块importstring,random,collectionsx=string.ascii_letters+string.digitsy=''.join([random.choice(x)foriinrange(1000)])count=collections.Counter(y)fork,vinsorted(count.items()):......
  • python根据时间字符串获取时间，判断是否非法定节假日时间
    fromdatetimeimportdatetimefromchinese_calendarimportis_workday,is_holiday,is_in_lieu,get_holiday_detail#定义两个时间字符串time_str1="2024-10-1218:41:02"time_str2="2024-10-1217:30:00"#将时间字符串转换为datetime对象time1=datetime.......
  • leetcode 刷题day43动态规划Part12（115.不同的子序列、583. 两个字符串的删除操作、72.
    115.不同的子序列思路：这个题还是比较有难度的，问题s中有多少个t子序列可以转化为s字符串中有多少删除元素的方式，使s可以变成t。考虑动规五部曲。1、确定dp数组（dptable）以及下标的含义dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。2、确定递推公式......
  • Python 如何美观地格式化字典字符串输出
    在本文中，我们将介绍如何使用Python来美观地格式化字典字符串的输出。字典是Python中重要的数据结构之一，它可以存储键值对，提供了一种方便的方式来组织和访问数据。当我们需要将字典的内容以字符串的形式输出时，往往需要对其进行适当的格式化，以便更好地阅读和理解。使用json.dumps()......
  • 洛谷题单指南-字符串-P1470 [USACO2.3] 最长前缀 Longest Prefix
    原题链接：https://www.luogu.com.cn/problem/P1470题意解读：求s最长前缀长度，使得可以拆解成p集合中的字符串解题思路：动态规划：设s字符串下标从1开始，p集合用set<string>保存所有的元素状态表示：设f[i]表示前i个字符s[0~i-1]是否能拆解成p中的元素状态计算：对于j=i-1开始往后倒......
  • [TJOI2019] 甲苯先生的字符串 题解
    T2[TJOI2019]甲苯先生的字符串矩阵乘法优化DP，所以一般来说这种DP都不怎么难。30pts的DP是裸的：设\(f_{i,j}\)为前\(i\)位、最后一位是\(j\)的方案数，则有转移方程：\[f_{i,j}=\sum_{k=0}^{25}f_{i-1,k}\landk\nej\]想要矩阵优化，我们想到构造答案矩阵：\[\mathit{an......
  • 代码随想录算法训练营第八天（1）|哈希表理论基础
    文档讲解：代码随想录难度：有一点哈希表理论基础哈希表首先什么是哈希表，哈希表（英文名字为Hashtable，国内也有一些算法书籍翻译为散列表，大家看到这两个名称知道都是指hashtable就可以了）。哈希表是根据关键码的值而直接进行访问的数据结构。这么官方的解释可能有点懵，其实......
  • [TJOI2019] 甲苯先生的字符串
    有点水了……考虑相邻的不能放在一起，不相邻的可以，那么很容易想到转移方程：\[dp_{i,j}=\sum_{k=0}^{25}dp_{i-1,k}[j,k不相邻]\]其中\(dp_{i,j}\)表示填了\(i\)位，最后一位填\(j\)。那结合数据范围，显然矩阵快速幂。时间复杂度\(O(26^3\logn)\)，可以通过#include<bits/std......
  • 洛谷题单指南-字符串-P5283 [十二省联考 2019] 异或粽子
    原题链接：https://www.luogu.com.cn/problem/P5283题意解读：n个整数，每次从从取l~r的数进行异或得到美味值，一共取k次，并计算这k个美味值之和的最大值。解题思路：1、如何O(1)的计算l~r数的异或，得到美味值可以借助前缀和思想，a[i]为第i个数，s[i]表示a[1]~a[i]每个数的异或值，要计算l~r的......
  • js-将JSON 字符串转换为JavaScript 对象（JSON.parse）
    1.背景//JSON字符串constjsonString='{"name":"张三","age":30,"city":"北京"}';获取name值2.JSON字符串进行转换为JS对象将JSON字符串转换为JavaScript对象(JSON.parse(jsonString))//JSON字符串constjsonString='......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99