题意
求多串的最长公共子串
串个数 \(\le 10\)，串长度 \(\le 1000\)
solution
好久不写SAM，于是打算打一打这个模板题。
首先建出多个串的SAM，对于每个节点，我们还需统计它是几个串的子串，因为这里串很少所以直接状态压缩即可。这一步直接在parent树上dp即可求出。最后的答案也就是每个串都有的子串中的最长长度。
主要来看建SAM时怎么初始化，这里分别来介绍trie或在线插入这两种主流建法怎么初始化。
在线建法
每次对于一个新串把上一次遍历到的最后位置设为SAM上的初始状态。然后直接类似普通的SAM插入，对于新建的节点，只有当前串包含这个节点的所有串，所以直接给当前串设成 \(1\) 即可。对于之前已经有的节点，就不能直接或上当前串了，要分类讨论，如果当前点可以放入这个串就直接或上，否则对于新建的点其值只有当前串。
trie树建法
这个做法就比较直观了，对于trie树上的每个节点就也搞一个压缩记录这个节点是几个串经过的。然后在新建节点时直接赋值即可。