AcWing 841 字符串哈希 题解（模板）（哈希表 Hash）
发布时间
阅读量：
阅读量
字符串哈希的基本原理是将每段字符串转换为P进制数值，并为其分配一个唯一的‘地址’，通过比较这些地址来判断字符串是否相同，该过程的时间复杂度为O(1)。而若采用逐个字符进行比对的方式，则时间复杂度将提升至与字符串长度成正比的O(字符串长度)。
#include<iostream>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5 + 10, P = 131;//P经验值131、1331
int h[N], p[N];//h数组储存以末尾字符为标志的每段字符串的特殊‘地址 ’，p储存P的幂
char str[N];
int n, m;
ULL get(int r, int l){
return h[r] - h[l - 1] * p[r - l + 1];//求第l到第r位之间字符串对应‘地址 ’的公式(推导过程问本人）
}
int main()
{
scanf("%d%d%s", &n, &m, str + 1);//后期处理字符串都是从1开始，所以读入字符串的下标也从1开始
p[0] = 1;//防止全部评论 (0)
还没有任何评论哟~