【OI之路】08暴力的学问-5哈希

哈希Hash

前言

这东西主要用来验重
而且在字符串领域比较常用
但其思想的应用才是其精髓
所以没有放在字符串分类

正文

1
2
3
4
5
6
7
8
9
10
11
12
typedef unsigned long long ull;
ull gethash(char *s)
{
int len=strlen(s+1);
ull ans=0,p=1;
for(int i=1;i<=len;i++)
{
ans=ans*p+s[i];
p*=13331;
}
return ans;
}

其他应用

1. 字符串匹配-kmp

例题:poj3461 Oulipo

2. 字符串匹配-ac自动机

等价于用kmp搞ac机,不推荐

3. 字符串匹配-manacher

O(nlogn)求最大回文子串
其实就是枚举中心点,分情况讨论,然后二分长度

4. 字符串匹配-后缀数组

O(n log^2⁡ n )
在排序的比较函数中,套一个二分,得到最长公共前缀,比较其下一个字符,就能够比较出大小
得出排名后,相邻的再同样地二分一次就好了

练习题

Tag-哈希

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/posts/9bde.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%