后缀自动机小结①

【cxjyxx_me是个大沙茶 他连后缀自动机这个pj算法都不会。。】
后缀自动机。。
这个算法我看了<仅是看 没包括写> 近一个星期= =
肯定是我太沙茶了=、=
先推荐几篇文章吧,,

①显然是clj的论文                              《陈立杰营员交流资料.pptx》
②后缀自动机初窥                                http://blog.sina.com.cn/s/blog_7812e98601012cim.html
③后缀自动机与线性构造后缀树          http://fanhq666.blog.163.com/blog/static/8194342620123352232937/

④后缀自动机(FHQ+Neroysq补完)   http://hi.baidu.com/myidea/item/142c5cd45901a51820e25039
⑤后缀自动机的应用                            http://blog.sina.com.cn/s/blog_7812e98601012dfv.html

因为我太弱了、  用了一个星期的时间吧他们每个至少看了三遍才大概理解sam(Suffix Automaton)..<其实好像还是不是很理解。。>

先说下我对后缀自动机的理解吧。。(其实只是阐述一些性质。。)
如果说AC自动机可以识别所有前缀 那么 后缀自动机则可以识别所有子串!
也就是从s的sam的根开始走
走到每一个节点的路径形成的字符串各不相同
且构成了串s的所有子串!<=这个性质很科学有木有~

用fail指针构成的树就是一棵后缀树 (其实是前缀树。。但是用起来没什么差)

构造的时间复杂度根据势能分析是线性 (势能分析是什么? 我怎么知道。。。)

然后我们要做得就是构造一个满足这些性质的图。。。<恕我沙茶的理解。。>

先给一个串aabbab的sam图
psb (44)

(蓝边代表fail指针)
一个节点代表的字符串集为从s到这个点的所有路径集合
可以发现对于一个节点 他代表的串集在s上区间如下
[l, r]
[l + 1, r]
[l + 2, r]

[l + k, r]
如节点4 他代表的字符串集:
[1, 4] = aabb
[2, 4] = abb
[3, 4] = bb
这里定义min和max为l的取值区间
如 min[4] = 1, max[4] = 3
定义right为r
如right[4] = 4

介绍一下fail指针
对于fail[u]=v
有right[u] = right[v], max[u] + 1 = min[v]
可以类比kmp里的fail数组
就是fail[u]就是跟u的后面一坨一样的点
如fail[4]=5
5代表
[4, 4] = b

这样我们发现fail构出了一颗”前缀树”
和后缀树相同 为了使每个前缀都是叶子节点 我们不妨在串s前加入一个没出现的字符’#’
这里为了配合上面的图 就不加这个#了 下面给出串aabbab按fail构出的前缀树
psb (47)
(红色为路径上的值 蓝色为从根到这个点 经过的路径串拼起来 即为点的值 注意 这里的拼起来是往前加。。 看一下应该能理解)

如果加上#的话 就会有这样一个性质:每个叶子都不一样 且构出所有前缀
而#并不影响sam的构造

构造一个sam 我们要知道一个结构体:
struct node
{
int l, f, ch[26];
}t[maxn];

其中
l表示 这个点代表的字符串集里最长的长度
f表示 fail指针
至于ch数组 在fail树上不妨这样理解:
对于t[i].ch[j] 定义串k为i这个节点代表的最长串后面加入字符j所得的字符串
t[i].ch[j]是一个以k为后缀(严格包含  即len[k] <= t[t[i].ch[j]].l)的l值最小的节点
比如ch[ab]在aab和aaab中会选aab
看下这个图吧。。 有点乱。。。
psb (50)

sam的构造方法是逐个字符添加 也就是说你在添加第i个字符时 1~i-1个字符的sam已经建立了
现在考虑怎么在这个以建立的sam上添加一个字符
这里记录一个变量last 表示上次添加的节点是哪个 比如这个sam的last=7

现在考虑在这个sam上添加一个字符b 即新加入一个值为aabbabb的节点
他应该找到一个是他的后缀的节点作为他的父亲节点 然后插入进去
怎么找这个呢?
如果t[last].ch[‘b’]有节点 那么就是他了
不然就是
t[t[last].f].ch[‘b’]
t[t[t[last].f].f].ch[‘b’]
…..(即last的一堆祖先).ch[‘b’]
直到找到一个ch[‘b’]是有节点的。。
另外要把一路上的last, t[last].f, t[t[last].f].f…的ch[‘b’]都设为now (now为新节点编号)
如果一直到根 连根的ch[‘b’]都没有节点 那就直接把t[now].f设为根
否则对于一个节点p他有ch[‘b’] 设c=t[p].ch[‘b’] (如图p=8 c=4)
如果c是now的后缀 那就喜闻乐见直接把now的fail设为c就可以了
否则 可以知道的是c和now共享长度为t[p].l + 1的后缀
那么就新建一个节点r 表示这个被共享的后缀
再把now和c都弄成r的儿子即可~(即把t[now].f和t[c].f赋为r)
然后还要把所有p及祖先的ch[‘b’]==c的ch[‘b’]全部赋为r(满足l最小定理)
这样就完成了一次添加操作。。
然后把整个字符串一个个加进来就行了。。。
代码如下:
—————————————-

void add(int k, int len)
{
  int now = ++l, p = last;
  last = now;
t[now].l = len;
  for (; p && !t[p].ch[k]; p = t[p].f) t[p].ch[k] = now;   //找到ch[k]不为空的节点 且边把路上的节点的ch[k]赋为now
  if (!p) t[now].f = 1;
  else
    if (t[t[p].ch[k]].l == t[p].l + 1) t[now].f = t[p].ch[k];
    else
    {
      int c = t[p].ch[k], r = ++l;
      t[r] = t[c];
      t[r].l = t[p].l + 1;
      t[now].f = t[c].f = r;
      for (; p && t[p].ch[k] == c; p = t[p].f) t[p].ch[k] = r;   //可以证明对于某个节点到根的路径上的点的ch[k]值 一样的一定连续
    }

}
———————————————
好像比我的sa短了一行。。难道不是莫大的讽刺?=、=
终于写完了。。 写得好像有点略乱= =
题目、应用什么的明天再说吧。。 有点晚了- –

后缀自动机小结①》上有2条评论

发表评论