数据结构

1. 哈希表
   哈希表:将高维稀疏点空间映射为低维点空间,如此做的好处是节省空间.
   算法题里一般只需要增查,删一般将元素打标记即可.
   哈希表的关键问题:1.确立哈希函数(一般是模一个数,这个数要求是质数且离2的n次幂尽可能远)
   2.处理冲突(拉链或寻址)
2. 哈希表:拉链法模拟
   关键参数:h[N]初始化为-1,e[N],ne[N],idx
   可以视为N个链表,其中h[N]存放的是头节点指针,也就是N个head,指向头节点地址idx,而并不是首个节点的哈希值逆
   操作: void insert(int x) ,bool find(int x)
3. 哈希表:开放寻址法
   关键参数:h[N],N往往取题中插入操作的2N~3N倍
   操作:find(int x)若x已在h[N]中返回x在其中的下标地址,否则发货x应该在h[N]中的地址.

算法

1. 字符串前缀哈希
   y总说十分牛逼,比kmp还猛
   将一个字符串的所有前缀根据p进制(131 or 13331)转化为一个整数.
   使用公式h[R]-h[L]*p^(R-L+1)即可算出L-R之间字符串的哈希值,进而可以在O(1)时间比较两字符字串串是否相同.
   nb!

小技巧与知识

• 学到了stl新花活儿bitset,将1bit,8位,每位存一个bool,也就是减少8倍内存

今日模板算法默写框架

拉链法
int h[N], e[N], ne[N], idx;
void insert(int x)
{
}
bool find(int x)
{
}
开放寻址法
int h[N];
int find(int x)
{
}
字符串哈希
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
}
ULL get(int l, int r)
{
}