2017 10 07
未分类

1、hash

将字符串变成整数O（1） RK-hash：把字符串看作一个base进制的数，对素数p取模 大整数取模

for （int i=1; i<=len; ++i） {
    hash[i] = (hash[i-1]*base+s[i])%p;
}

hash[i] 字符串到i的哈希值，前缀 base可以取31,131,13131 大于|西格玛| 把a看成1，不能是0,。 p一定是long
long 范围的一个素数10^18+9,23,333,333,333,333,333 unsigned long long 多找几个素数
mod p1 == mod p2 <==> mod p1p2 求任意一段的hash值， 123456 求345的hash值
12345-12000 l...r hash[r] - hash[l-1]*pow(base,r-l+1) == hash[l...r]
pow 可以预处理

求公共前缀 Poj 2758 暴力插入操作，hash+二分 异或，不能取子串的hash

2.Manachar

O（n）
首先将所有字符之间添‘#’ 以每个点向左向右延伸成为回文串的半径r[i] S[] = abcbaabcba R[] = 1131111311

//baoli for (int i=1; i<=len; ++i) {
r[i] = 1;
while (s[i-r[i]] == s[i+r[i]]) r[i]++; }

若是aaaaaaaaa...n^2

记录两个变量mx,id; 以id为中心向左向右最大能延伸mx的字符

for (int i=1; i<=len; ++i) {
r[i] = min(r[id-(i-id)],mx-i);
while (s[i-r[i]] == s[i+r[i]]) r[i]++;
if (i+r[i-1]>mx){
mx = i+r[i]-1；
id = i;
}
}

例题：

bzoj2342 双倍回文
bzoj3676 会问子串
exkmp

tyvi1068 当前位置：
aabcde
120000 以每个点
//暴力
ababababb
ababb
lcp：最长后缀

for (int i=1; i<=n; ++i) {
p[i] = 0;
while (b[i+p[i]==b[p[i]+1]]） p[i]++; } //O(n)

for (int i=1; i<=n; ++i) {
p[i] = min(mx-i,p[i-id]);
while (b[i+p[i]==b[p[i]+1]]） p[i]++;
if（i+p[i]>mx) {
id = i;
mx = i+p[i];
} }

EXKMP

思路与马拉车相似
要在上次最大匹配的边界内进行扩展
取MIN
水!!!!

trie树

用字符建立节点
开二维数组
第二维记录其儿子
令root=0；

AC自动机

把trie不存在的孩子用fail节点的孩子补出来
求fail指针;要是trie[i][x]存在，则fail[trie[i][x]]=trie[fail[i]][x].
否则，trie[i][x]=trie[fail[i]][x]