双数组字典树

0. 前置知识

需要提前有字典树的知识

1. 双数组字典树介绍

双数组字典树英文名为DoubleArrayTrie,他的特点就是使用两个数组来表示一颗字典树,这里有比较有趣了,两个数组是怎么表达出字典树的呢?

2. 双数组介绍

顾名思义,有两个数组,一个是base,另一个是check。

首先介绍数组的下标,数组的下标代表字典树上节点的编号,一个下标对应一个节点。

其实base数组的作用是用来记录一个基础值,这个值可以是随机值,只要不产生冲突就可以了,所以这个值可以用随机数算法获取,当然这样效率不高,高效的做法应该是使用指针枚举技术,ok,现在你已经明白了,base数组是一个不产生冲突的随机数组。

最后,check数组,check数组与base数组相互照应,如果base[i]=check[j] 则说明j是i的儿子,而且i到j的边权恰好为j-base[i],也可以写作j-check[j]好好理解这句话

从另一个方面而言,双数组字典树的base数组,应该是一个指针数组,他指向了一个长度为字符集大小的数组的首地址,而check数组是一种hash碰撞思路,由于base数组疯狂指向自己,导致产生了很多碰撞,但是由于字典树是一个稀疏图,导致儿子节点指针利用率低,所以base数组疯狂复用这段空间,最后必须要依赖check来解决冲突,

双数组字典树相比于传统字典树,仅仅只在内存方面于增删改查占有优势,但是唯一不好的地方就是删和改会导致base数组内存分裂,难以回收,删和改如果占大头,那么传统字典树的内存效率更高

由于搜索领域几乎不涉及到删和改,所以这个数据结构很nice,字符集多大,就节省了多少倍的空间

数据结构很棒,但是在现在这个内存不值钱的时代,这些指针的储存用hashmap直接无脑顶掉,空间占用也高不了多少,hashmap顶多浪费两倍空间

两倍的空间算不上啥,除非这是唯一的优化点,否则不会优化到这个数据结构上来

阅读更多

基数树

基数树

基数树是一种更加节省空间的数据结构,他是字典树的升华,

字典树的缺陷

常常字典树会很深,而不胖,这会导致空间的浪费,因为里面的指针很多,往往我们发现,如下列字典树
稍等片刻!正在将字符数据转化为图形

1
2
3
4
5
graph LR
start((start))--a--> 1((1))
1((1))--b-->2((2))
2((2))--c-->3((end))
2((2))--d-->3((end))

用基数树改进字典树

我们可以通过压缩字符路径为字符串路径,即将长链压缩为一条边。

1
2
3
4
graph LR
start((start))--ab-->2((2))
2((2))--c-->3((end))
2((2))--d-->3((end))

当然你甚至还能这样

1
2
3
graph LR
start((start))--abc-->3((end))
start((start))--abd-->3((end))

这些都是合法的基数树。注意,基数树仍然是字典树,只不过他压缩了路径

用基数树加速IP路由检索

路由检索常常是检索一个01字符串,这时候我们可以通过压缩的方式,每两位压缩、或者三位、四位压缩,能够让查找次数更少,当然这样做可能会牺牲空间,但是他依然是基数树优化的字典树。

后缀树

后缀树

一颗后缀树是针对一个字符串而言的,该后缀树能识别这个字符串的所有后缀,能且仅能识别这个字符串的所有字串,

后缀树空间压缩

常常我们会在后缀树的边上储存字符串,而不是字符,这样可以避免大量的内存开销,每一条边,我们都记录了两个数据,字符串的起点和终点,这样就实现了后缀树的空间压缩

后缀树的构造

后缀树有很多构造算法,这里直讲最简单的,考虑一个字符串的后缀自动机,其上的paerent树便是反串的后缀树。

trie

字典树

字典树是我接触自动机的开端,我们先讲自动机,

自动机

自动机有五个要素,开始状态,转移函数,字符集,状态集,结束状态。

自动机识别字符串

假设我们有一个自动机,他长这个样子,他能识别字符串abc.
稍等片刻!下图正在转码中

1
2
3
4
graph LR
start((start))--a--> 1((1))
1((1))--b-->2((2))
2((2))--c-->3((end))

最开始我们在位置start,也就是初始状态,当我们读入字符a的时候,经过转移函数我们到达了1号状态,如果我们在初始状态读到的是字符b,则因为初始状态没有字符b的转移函数。会导致自动机在非终结状态停机,这就意味着无法识别字符b,同理也无法识别c-z,于是在初始状态只能识别a,

然后分析状态1,只能识别b,到达状态2,只能识别c到达终态。最后就识别了字符串abc。

然后我们来考虑一个复杂一点的自动机,他能识别字符串abc、abd、bc、ac

稍等片刻!下图正在转码中

1
2
3
4
5
6
7
8
graph TB
start((start))--a--> 1((1))
1((1))--c-->10((end))
start((start))--b--> 3((3))
3((3))--c--> 10((end))
1((1))--b-->2((2))
2((2))--c-->10((end))
2((2))--d-->10((end))

如果我们不去分析其中的end节点,他的本质就是一颗树,他同时又叫做字典树,特别的,如果这个字典树的字符集为01,则他又叫做01字典树。

字典树的插入

字典树的插入应该是一个字符串,这个过程我们可以用递归实现,

字典树的删除

特别注意,为了能够支持多重集合,我们常常用一个数字来代表有多少个字符串在某个状态结束,这样删除的时候只要减少那个值就可以了

字典树的查找

递归。

递归转非递归

因为字典树的代码特别简单,我们常常直接用递归转非递归来实现。

代码

先欠着,暂时拖一个不太友好的代码在这里,这里面有一部分代码就是字典树啦。
代码链接

后缀自动机

前言

本文力争用理性分析的手段,来推测此算法发明者的思维过程, 尝试感受其在设计此算法的时所展现出的思维方式, 力求用数学证明的手段,尽可能多的为读者证明相关结论,建议有其他自动机学习的基础,最好已经学会AC自动机和回文自动机,后缀自动机很难,他 和其他自动机不一样,它的状态更加复杂,一个算法的创作过程很 复杂,学起来当然会感到很难。强烈建议看陈立杰的ppt,看一遍肯定看不懂,仔细看,一遍看不懂看多遍,第一次可能只能看懂几面,第二次可 能就能看懂到十几面了,慢慢的就全懂了。

阅读更多

Manacher算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct Manacher {//鉴于马拉车算法较复杂,此处有少量修改,
//s[i]=ma[i<<1]
//mp[i]表示以i为中心的最长回文串的半径,且mp[i]-1恰好为此回文串包含原字符串的字符的数量
//可以证明ma字符串所包含的回文串总数=原字符串b所包含的回文串总数+2n+2
static const int maxn = 1e6 + 666;
char ma[maxn << 1];
int mp[maxn << 1], begat[maxn];//begta[i]-> 以i开头的回文串的数量 begin at

void build(char *str) {
int len = strlen(str + 1), l = 0;
ma[l++] = '$';//$#.#.#.#.#.#.#.#
ma[l++] = '#';
for (int i = 1; i <= len; i++) {
ma[l++] = str[i];
ma[l++] = '#';
}
ma[l] = mp[l] = 0;
int mx = 0, id = 0;
for (int i = 0; i < l; i++) {
mp[i] = mx > i ? min(mp[2 * id - i], mx - i) : 1;
while (ma[i + mp[i]] == ma[i - mp[i]])mp[i]++;
if (i + mp[i] > mx) {
mx = i + mp[i];
id = i;
}
}
//for(int i=2;i<=l;i++)palindrome+=mp[i]>>1;//回文串个数

//若不用dalt数组,此后可删掉
for (int i = 1; i <= len; i++)begat[i] = 0;
for (int i = 2; i < l; i++) {
int s = i - mp[i] + 1;//ma串最长回文左端点s
s = (s + 1) / 2;//变为str串最长回文左端点,向上取整,因为str[i]对应smp[i<<1]
int t = s + mp[i] / 2 - 1;//右端点
begat[s]++;
begat[t + 1]--;
}
for (int i = 1; i <= len + 1; i++)begat[i] += begat[i - 1];//+1是为了还原
}
};

AC自动机

AC自动机

所谓AC自动机,其实是kmp算法与字典树的结合,不懂这两个,是无法学会的。

自动机

自动机,是一个五元组,包括了状态的非空有穷集合,符号的有限集合,状态转移函 数, 开始状态,终止状态集合,而在字典树上,增加了两个新的东西,一个标记了终止状态集合,另一个辅助了状态转移函数。 我们利用字典树上 的节点来表示状态,而边则用来表示状态转移函数的一部分。

阅读更多

回文自动机

回文自动机,就像AC自动机一样,他采取字典树来储存状态集合,也像AC自动机是KMP 算法与字典树结合一样,回文自动机就是manacher算法和字典树结合的新算法。

在回文自动机里面,状态指的是,以字典树上所表示的字符串的逆序串的以末端字符镜像对称后得到的新串,简单说,baab在字典树上为root->a>b,cacaacac在字典树上为root->a->c->a->c,想像根就是对称中心,往儿子走就意味着,在对称中心两端加上同样的数字。当然这样子是无法表示奇数回文的,所以我们设立两个根就可以了。一个串的回文自动机,储存了这个串的所有回文子串。

回文自动机的状态转移的依据是回文,举个例子,如下图,如果黑色串代表以黄色字符为结尾 的最长的回文串,红色串代表黑色串的最长真后缀回文串,(定义:若回文串a为某串b的真后缀,则a为b的真后缀回文串,定义:若后缀a为某串b的后缀且 a!=b,则a为b的真后缀)当我们在黑串后面加上一个绿字符形成新串的时候,(姑且叫他黑绿串)回文自动机中的节点会发生什么样的变化呢?显然增加了 某些新的回文串,但是我们考虑这样一个事实,如果我们把黑绿串的最长后缀回文串加入到自动机中以后,我们就把黑绿串新增的所有回文串都可以被回文自动机所表示,证明类似于manacher算法,请自行证明。

下面来讨论如何把它加进去。我们假设粉色字符刚好是是红色串前的一个字符,如果粉色字符和绿色 字符为同一个字符的时候,我们可以肯定,黑绿串的最长真后缀回文串就是粉色字符+红串+绿色字符。此刻我们只需要新增一个节点了。如果他们不相等的话,重复 我们对黑串的算法与红串之上即可解决。

然后我们来考虑新增节点的所表示的回文后缀的最长真后缀回文串,我们重复使用上一段的算法,即可找到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
struct palindrome_tree{
    static const int maxn=1.2e5+5;
    int trans[maxn][26],len[maxn],suf[maxn],num[maxn];
    //len代表回文长度,suf指向回文后缀,类似于fail指针,num是最长后缀的数量,经过calc之后是后缀数量
    int last,cnt;//last是上一个回文后缀,cnt是所有节点数
    
    int new_node(int _len,int _suf,int _num){//长度,后缀,数量
        for(int i=0;i<26;i++)trans[cnt][i]=0;
        len[cnt]=_len;
        suf[cnt]=_suf;
        num[cnt]=_num;
        return cnt++;
    }
    
    void ini(){
        cnt=0;
        int root_even=new_node(0,1,0);//=1
        int root_odd=new_node(-1,1,0);//=0
        last=root_odd;
    }
    
    int query_longest_palindrom(){
        int ret=1;
        for(int i=0;i<cnt;i++){
            ret=max(ret,len[i]);
        }
        return ret;
    }
    
    void build(char*s){//s是要建立回文自动机的字符串,下标从1开始
        int len=(int)strlen(s+1);
        for(int i=1;i<=len;i++)extend(s,i);
        calc();
}
    
    void extend(char*s,int cur){
        int w=s[cur]-'a';//当前结点的值
        int p=last;//上一次匹配到的回文后缀
while( cur-len[p]-1<1 || s[cur-len[p]-1] != s[cur]) p=suf[p]; // BUG 数组越界
        //现在p结点的cur儿子,要么是匹配成功的最长非自身回文后缀,要么是自身这一个字符
        
        if(!trans[p][w]){//如果此回文后缀未出现过,要创建节点
            int v=suf[p];//我们来找他的suffix link回边,
            while( s[cur-len[v]-1] != s[cur] )v=suf[v];
            //此时意味着找到了suffix link 是v的儿子
            trans[p][w]=new_node(len[p]+2,trans[v][w],0);
        }
      
        last=trans[p][w];//这一次匹配到的回文后缀
        num[last]++;
    }
    
    void calc(){
        for( int i=cnt-1;~i;i-- )num[suf[i]] += num[i];//结点创建顺序保证了suf[i]<i
    }
};

错位比较

codeforces 1043B

本质上让你求一个字符串可能的循环节,题目的第二个样例可以看作求序列 1,2,2,1,2,的循环节显然可以是3或5, 于是算法出来了,我们只要求出最小的循环节就可以了,最小的循环节怎么来求呢,我们hash预处理原字符串以便后面O1查询区间hash值,对于字符串s如下图,我们对原字符串复制一份,错位比较红色竖线之间的子串,如果相等,意味着什么读者可以自行思考,于是我们已经找到了On的做法了,我们只要从小到大枚举 蓝色区域即可

后缀数组

定义:

先定义一个字符串s,假设它的长度为n,s[i]表示第i个元素 ,s[i…]代表以s[i]开头且包含s[i]的后缀。我们定义新的数组 sa[i]为一个0-n的排列,且sa[i]为后缀s[i…]在所有后缀中按 照从小到大排序的排名。最后定义rank是sa的反函数。

sa数组也称为后缀数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//定义以s[i]开头的后缀是suf(i)
//后缀数组性质:suf(sa[i])<suf(sa[i+1])
//模版从下标为1的地方开始,引入的字符串下标也要从下标为1开始

struct SA{
static const int MAXN=2e5+555;
static int lg[MAXN];
int h[MAXN][20],rank[MAXN],sa[MAXN],n;

void init(char*s,int len){//第一个参数要是从下标为1开始的字符串,第二个参数是要从下标为
static int x[MAXN],y[MAXN],c[MAXN];//全部是辅助数组
n=len;//初始化后缀数组内部的n->s后缀数组长度
int m=1000;//桶的大小
for(int i=1;i<=n;i++)sa[i]=y[i]=0;//初始化sa,y
for(int i=1;i<=n;i++)x[i]=s[i];//把s复制到x
for(int i=1;i<=m;i++)c[i]=0;//初始化c
for(int i=1;i<=n;i++)c[x[i]]++;//对x计数
for(int i=1;i<=m;i++)c[i]+=c[i-1];//计数前缀和
for(int i=n;i>=1;i--)sa[c[x[i]]--]=i;//按照计数排序后的结果
for(int k=1;k<=n;k<<=1){
int num=0;
for(int i=n-k+1;i<=n;i++)y[++num]=i;
for(int i=1;i<=n;i++)if(sa[i]>k)y[++num]=sa[i]-k;
for(int i=1;i<=m;i++)c[i]=0;//初始化c
for(int i=1;i<=n;i++)c[x[i]]++;//对x计数
for(int i=1;i<=m;i++)c[i]+=c[i-1];//计数前缀和
for(int i=n;i>=1;i--)sa[c[x[y[i]]]--]=y[i];
for(int i=1;i<=n;i++)y[i]=x[i];
for(int i=1;i<=n;i++)x[i]=0;
num=1;
x[sa[1]]=1;
for(int i=2;i<=n;i++){
if((y[sa[i]]!=y[sa[i-1]])||(y[sa[i]+k]!=y[sa[i-1]+k])){
x[sa[i]]=++num;
}
else x[sa[i]]=num;
}
if(num>=n)break;
m=num;
}
for(int i=1;i<=n;i++)rank[i]=x[i];
//获取高度数组
int k=0;
for(int i=1;i<=n;i++){
if(k)k--;
int j=sa[rank[i]-1];
while((i+k<=n)&&(j+k<=n)&&(s[i+k]==s[j+k]))k++;
h[rank[i]][0]=k;
}
//对高度数组做rmq
for(int j=1;j<20;j++){
int d=1<<j;
for(int i=1;i+2*d-1<=n;i++)h[i][j]=min(h[i][j-1],h[i+d][j-1]);
}
if(lg[1]!=0)for(int i=1;i<MAXN;i++)lg[i]=trunc(log(i+0.5)/log(2));
}

int lcp(int x,int y){//注意没有下标检查,如果访问越界的话,会错。
int L=min(rank[x],rank[y])+1;
int R=max(rank[x],rank[y]);
int k=lg[R-L+1];
return min(h[L][k],h[R-(1<<k)+1][k]);
}
}sa;
int SA::lg[SA::MAXN];