LINK：Typewriter
好久没写SAM了 什么都给忘了.
写了大概2h.感觉被卡常还看了题解.
考虑dp 然后容易想到维护前面的一个j决策 尽可能小.
然后每次考虑向后加一个字符 不过不行就跳父亲.
我的做法是先建立SAM 然后每个点维护right集中最小的就可以维护决策了.
常数大的很.
考虑不这样做 边建SAM边做dp.
然后每次维护指针j 如果now接不上下个字符 j就向后移动.
注意跳父亲 值得注意的是跳父亲需要写while 大概是因为可能会分裂的缘故。
这个点在没分裂之前是可以直接跳到那个父亲的 分裂之后需要跳两次 而且此时要>=
这一点我始终没想到 最后才看出来 SAM还得多刷几道题来巩固一下 自己有的时候的思维漏洞.