OI字符串 简单学习笔记
持续更新qwq（现在只抄写了后缀自动机）
SAM后缀自动机
以下内容摘抄自这里
- endpos
endpos是一个子串结束为止组成的集合。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。对于所有结束位置相同的字串，也就是endpos相同的两个子串。他们一个一定是另一个的后缀
两个字符串如果有一个是另一个的后缀，那么较长串的后缀一定是较短串的endpos的子集
两个字符串如果没有后缀的关系，那么他们的endpos的交集一定是空集
后缀自动机的每个节点是依照endpos来划分的，对于endpos相同的子串，我们可以划分在一起。所以我们不难得出一点，对于一堆endpos相同的子串，他们一定互为后缀，并且他们的长度连续。
既然后缀连续，那就一定有一个最长的串，不妨记为longest。那么，所有的其他串一定是它的后缀。随着后缀长度的减小，那么从某一个后缀开始，就可能出现在了更多的位置。那么买这个后缀以及比它更短的后缀的endpos一定会变大，此时他们就会分到别的节点去了。
确定了endpos和长度len就能确定唯一的子串
- trans
trans是转移的意思，设trans(s,c)表示当前在s状态，接受一个字符c之后所到达的状态。一个状态s表示若干endpos相同的连续子串。
那么此时相当于在后面加上了一个字符c。那么我们对于任意一个串直接加上一个字符c之后，组成的串的endpos还是相同的。所以trans(s,c)就会指向这个状态。
- parent/suffix links
不妨设一个状态中包含的最短的串叫做shortest。那么我们就知道shortest的任意一个非自己的后缀一定就会出现在了更多的位置。它的那个最长的后缀，也就是减去了第一个字符后的串，就会出现在另外一个状态里，并且是那个状态的longest。
parent tree上，每一个点集的父亲都是自己的后缀。
假设当前状态为s，\(s.shortest.len=parent.longest.len+1\)
所以对于每个状态，没有必要记录shortest，因为你只要知道parent就可以算出来了。
s的endpos是parent的子集
这个不难证明，因为parent包含了更多的位置。
如果trans(s,c)不等于NULL，那么trans(parent,c)不等于NULL
parent是一个完全包含了s的状态，也正因为如此，parent的endpos就是所有儿子endpos的并集
将所有的parent翻过来，我们就得到了parent树。如果要处理什么，就需要parent树的拓扑序。（因为parent相当于包含了它的所有子树，都需要更新上去）。。。不过其实不需要拓扑排序，我们知道s的endpos完全被parent的endpos包含，所以s.longest一定长于parent.longest。所以一个状态的longest越长，它一定要被更先访问。所以，按照longest的长度进行桶排序就可以解决拓扑序了。
- extend
对于一个SAM的构造，我们依次加入字符c，来进行构造。
假设原来的字符串是T，首先一定会有一个新节点。因为新加入了一个字符后，一定出现了这个新的字符T+c。此时的endpos一定是新的位置。同时，原来的T的最后一个位置也可以通过+c变到这个新位置。设原来的最后一个位置的状态是last，新的状态是np。所以tans(last,c)=np。
根据前面的东西，我们知道last的祖先们一定也会有这个trans，之后来解决这个问题——
令p=last，一直沿着parent往前跳，也就是不断令\(p=p.parent\),所以p所代表的的，就是越来越短的T的后缀。因为要更新的是最后的位置。只有当存在T的最后一个位置的时候才能更新。
如果\(trans(p,c)=NULL\)，直接令\(tans(p,c)=np\)。很显然是可以在后面添加一个c到达np的，如果跳完之后发现没有parent了，直接把np.parent指向1（也就是空串所代表的状态）
如果某个\(trans(p,c)\)不等于NULL，那么设\(q=trans(p,c)\)——
如果有\(longest(p)+1=longest(q)\)，那么我们在p的串后面直接添上一个c之后就是q状态。没有任何问题，直接在作为T的后缀的那一个子串上，直接添加一个x显然也可以到达q状态，又因为np所代表的endpos更小，所以\(np.parent=q\)。
否则的话，也就是\(longest(q)>longest(p)+1\)（也就是前面那个while更新的时候可能会导致的情况）。如果直接插入的话，相当于给q的endpos强行插入一个np,但是我们发现，如果强行插入进去，这个T+c的后缀会出现在更多的位置，应该属于另外一个状态，不太行。
所以我们新建一个节点nq，相当于把q拆成两部分：一部分是T+c的那个后缀，一个是\(longest(p)+c\)，也就是\(longest(nq)=longest(p)+1\)，显然T+c的后缀是包含了状态较少的，拆分出来的一部分q是长度较长的。所以\(q.parent=np.parent=nq\)。同时，继续沿着p的parent往上走，把所有的q都替换成nq。
比如对于字符串S="aabbabd"，它的后缀自动机是：
