后缀自动机、广义后缀自动机备忘录
前言
话说这玩意一两年前就会了。
然后太久没打了，都忘光了。
今天又有题要用这玩意儿，就再康了康。
话说稍微看了看记忆就又回了了。
还是要多复习啊。
后缀自动机
简称SAM。
以前还有个老话是“初三还不会SAM就退役把”
不多废话。（话说上面的不都是废话吗）
定义
后缀自动机就只是定义比较难理解而已。
- 1、定义endpos数组表示某个子串在主串中出现的位置集合。
- 举个例子就是abcabcabcaac，那么endpos(abc)={3,6,9}
- 1.5、定义一个自动机上节点的right表示当前点endpos集合相同的子串的集合。
- 2、定义maxlen和minlen表示自动机上一个节点上right集合的长度最大最小值。
- 3、定义fail指针（没有fail指针就是没有自动机的灵魂）
- 设当前节点为y，fail指针指向的位置为x。
- 那么x满足x的right集合真包含y的right集合。
- 且若有多个x满足上面条件，则x选择maxlen最大的那个。
性质
- 1、显然如果两个字串的endpos全部相等，那么必然其中一个是另一个后缀。
- 2、那么我们发现在maxlen和minlen这个区间内的字符串都是互为后缀的且连续。
- 3、