首页 > 其他分享 >字符串hash

字符串hash

时间:2024-02-06 23:44:51浏览次数:34  
标签:1000010 hash int long 131 字符串

记录
23:40 2024-2-5

1. 字符串hash

将字符串转换为hash值。以p=131/13331,将字符串看成P进制数,取一固定值M,求出该P进制数对M的余数,作为该字符的hash值。
可以取M = \(2^{64}\) 用 unsigned long long存储这个hash值,这样不用取模,因为如果溢出了就相当于对\(2^{64}\)取模了

除了在极特殊构造的数据上, 上述 Hash 算法很难产生冲突, 一般情况下上述 Hash算法完全可以出现在题目的标准解答中。

点击查看代码
// s字符串
char s[1000010];
// f 前缀字符串的哈希值 p 131^i
unsigned long long f[1000010], p[1000010];
int n, q;
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	cin >> q;
	p[0] = 1; // 131^0
	for (int i = 1; i <= n; i++) {
		f[i] = f[i-1] * 131 + (s[i]-'a'+1); // hash of 1~i
		p[i] = p[i-1] * 131; // 131^i
	}
	// hash of [l, r]
	// f[r] - f[l-1] * p[r-l+1]
}

题目记录

标签:1000010,hash,int,long,131,字符串
From: https://www.cnblogs.com/57one/p/18009026

相关文章

  • 并发容器【ConcurentHashMap、CopyOnWriteArrayList、阻塞队列、ArrayBlockingQueue】
    (并发容器)转自极客时间什么是并发容器?在JUC包中,有一大部分是关于并发容器的,如ConcurrentHashMap,ConcurrentSkipListMap,CopyOnWriteArrayList及阻塞队列。这里将介绍使用频率、面试中出现频繁的最高的ConcurrentHashMap和阻塞队列。注意:这里说到的容器概念,相当于我们理解中......
  • ORACLE_查询blob字段中是否包含某个字符串/blob字段模糊匹配
    要查询一个BLOB字段中是否包含某个字符串,可以使用Oracle的DBMS_LOB.INSTR函数。示例如下,这里我们有2条记录,每条blob字段都有数据;其中第二条blob字段包含有字符串“T_NT_EndorsementBillEntry”,第一条记录没有正常我们如下查询会报错:对这个blob截取也会报这个错,这里我......
  • (11/60)有效的括号、删除字符串中所有相邻重复项、逆波兰表达式求值
    有效的括号leetcode:20.有效的括号实现思路遍历到左括号,入栈对应的右括号(方便遍历到右括号时进行对比);遍历到右括号,对比栈顶元素。把无效三种情况照顾到:1.左括号多了(遍历结束后栈不为空);2.左右括号不匹配(右括号时栈顶元素与当前元素对比);3.右括号多了(右括号时栈是空的)。复......
  • 32-Java中字符串、json、map之间的互相转换
    Java中字符串、json、map之间的互相转换 1.map转String、jsonObject对象packagemap;importjava.util.HashMap;importjava.util.Objects;importcom.alibaba.fastjson.JSON;importcom.alibaba.fastjson.JSONObject;publicclassMapDemo3{publicstatic......
  • 题解 ARC171D【Rolling Hash】
    来补题了。昨天赛时想法是对的,代码写错了,没调过太可惜了。显然\(P>n\)时必定有解。设前缀\([1,i]\)的哈希值为\(s_i\),显然\([l,r]\)的哈希值不为\(0\)的充要条件是\(s_{l-1}\nes_r\)。建立一个点的编号为\(0\simn\)的图,对于每个输入的区间\([l,r]\),连接一条边......
  • Python正则表达式实战:提取字符串中的数字
    在文本处理中,有时我们需要从字符串中提取数字,并去除其他非数字字符。Python中的re模块提供了强大的正则表达式功能,可以帮助我们实现这一目标。本文将介绍如何使用Python的re模块来提取字符串中的数字,以及如何应用正则表达式进行文本处理。第一步:导入所需库和模块在开始之前,我们首先......
  • Erlang 学习之第三天 . 函数,模块,递归,数字,字符串
    Erlang函数Erlang是一种众所周知的函数式编程语言,因此您将看到许多关于函数如何在Erlang中工作的重点。本章介绍如何使用Erlang中的函数完成所有操作。直接上实例:定义函数add(X,Y) ->    Z = X+Y,    io:fwrite("~w~n",[Z]). start() ->    add(5,6).......
  • HASHTEAM 强网杯 2024 WP
    2023强网杯强网杯疯狂坐牢,pwn做不了一点只能在强网先锋划划水....太菜了,来年再战!CryptoNotonlyrsa开就完了,直接上代码fromCrypto.Util.numberimport*fromtqdmimporttqdmn=6249734963373034215610144758924910630356277447014258270888329547267471837899275103......
  • 找到字符串中所有字母异位词
    问题描述:给定一个字符串s和一个非空字符串p,找到s中所有是p的字母异位词的子串,返回这些子串的起始索引。字符串只包含小写英文字母,并且字符串s和p的长度都不超过20100。说明:字母异位词指字母相同,但排列不同的字符串。不考虑答案输出的顺序。示例1:输入:s:"cbaeba......
  • HASHTEAMn1ctf2023WP
    N1CTF2023排名25,卡线Cryptowarmupnonce有问题数学模型:e=2^128*e1+e2d=2^128*d1+d2nonce=2^128*e1+d1s=(e+rd)/noncemodn展开s2128*e1+s*d1=2128e1+e2+r(2^128d1+d2)modn(s-1)2128*e1+(s-r*2128)d1-r*d2-e2==0modn造格子注意到d最高2^255一定为1,卡下界SM4......