首页 / 算法 / 后缀自动机构造算法学习笔记
后缀自动机构造算法学习笔记
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了后缀自动机构造算法学习笔记，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1650字，纯文字阅读大概需要3分钟。
内容图文
后缀自动机构造算法学习笔记
本文是笔者学习过程中的一些心得体会，不是从入门讲起的，请各位谅解
首先解释一下概念，"后缀自动机"是指的可以识别字符串所有后缀的有限状态自动机。
而我们平时做题用的后缀自动机叫做最简状态后缀自动机。
一个字符串的后缀自动机不唯一，但是最简状态后缀自动机唯一！
后缀自动机的线性构造算法
后缀自动机的构造算法是在线的增量更新。
考虑每次新加入一个字符\(x\)，我们需要做的是在保证时空复杂度的基础上构造出新形成的后缀
假设当前的字符串为\(L\)，我们列出right集合中含有\(|L|\)的所有状态，设其为\(v_1, v_2, \dots, v_k\)
一个显然的构造思路是我们可以在这些状态后面都加一条\(x\)出边，但是这样的状态数就是\(n^2\)的了。因此我们需要利用之前的状态进行压缩，然而对于不含\(x\)出边的状态，我们仍然需要引出一条\(x\)的出边。
考虑第一个含有\(x\)出边的状态\(p\)，在这之后的状态因为表示的都是\(p\)状态的后缀，因此他们也一定含有\(x\)出边。我们考虑想办法用这些出边表示之后的新后缀
接下来就是经典的关于\(len[p]\)与\(len[q]\)的讨论
如果\(len[p] + 1= len[q]\)，那么说明\(q\)节点可以作为新的可接受节点，直接把最后添加的节点的father设为q即可
举个例子。
考虑往ab后面加入字符a
它的SAM会变成这个样子
我们来模拟一下a加入时的过程
首先从\(3\)引出一条a边。
接着跳到父亲\(1\)号点，发现其含有a边连向的节点\(2\)，且\(len[2] = len[1] + 1\)，那么直接让\(fa[a] = 2\)即可。
这样不会有任何问题。
但是考虑如果是往ab后面添加b，它的SAM会变成这样
我们来模拟一下他的添加过程
首先从\(3\)引出一条b边。
接着跳到父亲\(1\)号点，发现其含有b边连向的节点\(3\)，但是这个时候\(len[3] > len[1] + 1\)，说明我们不能直接连接。加入我们连接了会发生什么呢？
这个时候\(3\)号节点会同时表示字符串ab与b，显然这两者的right集合是不同的(前者是\(\{2 \}\)，后者是\(\{2, 3\}\))
参考资料
内容总结
以上是互联网集市为您收集整理的后缀自动机构造算法学习笔记全部内容，希望文章能够帮你解决后缀自动机构造算法学习笔记所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。