【后缀自动机学习笔记】

前言

历经两天，看了大大小小的后缀自动机的知识讲解，看来看去，还是觉得HihoCoder上的SAM系列讲解的最白话最让人容易理解。
HihoCoder 讲解是按照 问题提出—>引入SAM概念---->模拟SAM---->构造SAM 这个顺序进行的，适合入门看。
放一下链接：进入网页后，点里面的解题方法提示即可
后缀自动机·基本概念
 后缀自动机·构造
PS：推荐各位认真阅读上述教程即可，该博文是本人对SAM的笔记，可能为了简便和适用自己，一些地方没有进行过多注解，请谅解。

学习笔记

后缀自动机（SuffixAutoMation）属于后缀家族的一员。
后缀自动机其实是一个DAG（有向无环图），其中各个结点是状态，边代表状态之间的转移。
它是一个DFA（有穷自动机），学过编译原理的童鞋应该会熟悉
我们把一个串建好它的自动机，那么该自动机可以识别该串的所有后缀。
自动机有一个S（初态），一个E（终态）
【后缀自动机学习笔记】

首先知道两点：

从S出发沿着蓝色实验路径转移，到达最终态，得到的是S的后缀。即S的后缀都可以从以S为起点，状态9（终态）为终点的路径中表示出来。
S的任一子串，都是以S为起点，终点为某一合法状态所表示出来的，因为串后缀的前缀是该串的子串。

对构造的一些理解：

trans[st][ ] 数组表示st的转移函数
比如last是上一状态，np是当前要加入的状态，x是新加入的字符
那么trans[last][x] = np 表示状态last到np状态的转移
slink[st] 数组表示st的Suffix Link，即转移序列，图中的绿色虚线。
比如图中：7 ----> 8 ----> 5 ----> s。他的意义是状态7的最长子串aabbab的后缀依次在状态7，8，5，s中。用Suffix Link表示这一串状态连接起来。
SAM的构造离不开这两个关键数组，构造复杂度为O(length(s))。采用增量法进行构造，即一个个字符的加入自动机。

自己对构造代码的注解：

struct SuffixAutoMation
{
   int last,cnt;
   int trans[maxn<<1][26],slink[maxn<<1],l[maxn<<1];
   void add(int x)
   {
   	//当前状态为np,上一状态为last, np的最长子串长度为last的最长子串长度+1,因为np是从last加了字符x转移过来的
   	int p = last,np = ++cnt; last=np; l[np]=l[p]+1;
   	//利用slink数组更新trans数组,即last所在的Suffix link序列中的后缀,都可转移至状态np
   	for(;p&&!trans[p][x];p=slink[p]) trans[p][x] = np; //注意p的意义在此循环中已经变成了Suffix link序列中,last的上一后缀所在的状态
   	//如果p为0,说明已走过了空串状态(1表示初态),初态的endpos集合肯定包含np的endpos集合
   	if(!p) slink[np] = 1;
   	//否则
   	else
   	{
   		int q = trans[p][x];
   		//如果q所包含的最长子串就是p的最长子串加上字符x,即maxlen[p]+1等于maxlen[q]
   		//只要增加slink[np] = q即可
   		if(l[p]+1 == l[q]) slink[np] = q; 
   		//否则
   		else
   		{
   			//从上一状态中拆分出来新状态,把字符x及其后缀分给新状态，其他子串留给上一状态
   			int nq = ++cnt; l[nq]=l[p]+1;
   			//同时更新trans和slink数组
   			memcpy(trans[nq],trans[q],sizeof(trans[q]));
   			slink[nq] = slink[q];
   			slink[q] = slink[np] = nq;
   			for(;trans[p][x] == q;p = slink[p]) trans[p][x] = nq;
   		}
   	}
   }
   void build()
   {
   	scanf("%s",s+1);
   	int len = strlen(s+1);
   	last = cnt = 1;
   	for(int i=1;i<=len;i++) add(s[i]-'a');
   }
}sam;

目前先更新到现在2018.10.17

【后缀自动机学习笔记】

相关推荐