后缀自动机入门/基本概念

教程链接
&＃xff08;本文为适应自己的理解&＃xff0c;对原文做出删改&＃xff0c;建议到原文学习&＃xff09;

后缀自动机可以干啥&＃xff1f;

后缀自动机&＃xff08;SAM&＃xff09;可以解决许多字符串相关问题。是一个特别nb的数据结构。它可以&＃xff1a;

1.在另一个字符串中搜索一个字符串的所有出现位置。
2.计算给定的字符串中有多少个不同的子串。

SAM是啥&＃xff1f;

》》SAM是一个有向无环图。节点被称为状态&＃xff0c;边就是状态之间的转移。
》》图存在一个源点t0t_0t0​ &＃xff0c;称作 初始状态 &＃xff0c;其它各结点均可从 出发到达。
》》每个边上表示一个字母&＃xff0c;类似边权&＃xff0c;从一个节点出发的所有边字母都不同。
》》存在终止状态 。如果我们从t0t_0t0​ 出发&＃xff0c;最终转移到了一个终止状态&＃xff0c;则路径上的所有转移连接起来一定是字符串的一个后缀。 字符串的每个后缀均可用一条从t0t_0t0​到某个终止状态的路径构成。
》》最后以最少的节点构成上述的数据结构&＃xff0c;我们就得到了一个后缀自动机。

SAM记录了字符串的所有子串信息&＃xff0c;SAM上的任意一个从t0t_0t0​出发的路径都是它的子串&＃xff0c;每个子串都在SAM上找到一个对应路径。

构造SAM&＃xff1f;

参考原教程图示即可理解。&＃xff08;做图太麻烦 &＃xff09;

我们引入$endpos(t)$为字符串中t出现的位置。如&＃xff1a;“abcbc” 我们有$endpos(“bc”)\&＃61;2,4$
如果两个不同子串的$endpos$可能相等&＃xff0c;我们把他们归为一个等价类。我们把这些等价类数量累计&＃xff0c;然后&＃43;1,就是这个SAM的总状态数。我们可以用这个假设构造SAM。
对于这个$endpos$我们可以很容易的理解它的几个性质&＃xff1a;

如果有两个endpos相同的子串&＃xff0c;则存在一个肯定是另一个的后缀。

扩展一下&＃xff1a;

如果有两个子串u和v&＃xff0c;&＃xff08;设|u|<&＃61;|w|&＃xff09;则它们的endpos只有两种情况&＃xff1a;
1.$endpos(u)\cap endpos(w)\&＃61;\varnothing$
2.$endpos(w)\subseteq endpos(u)$
这由u是不是w的一个后缀决定。

后缀链接link
我们想象一个SAM的一个非空状态v,我们通过前面的学习&＃xff0c;知道了v应该属于某endpos等价类。定义其中最长的一个子串为w。则&＃xff0c;等价类其他的字符串都是w的后缀。另外&＃xff0c;我们也知道&＃xff0c;w的后缀构成的endpos等价类都把w构成的这个等价类包含在内。这时我们设一个w的最长后缀t。令t满足&＃xff1a;
$endpos(w)\subset endpos(t)$
然后将v的后缀链接到t上。一个$link(v)$应该链接到对应于w的最长后缀的另一个endpos等价类的状态。则这些链接构成一棵树。
图示见原教程