要求构造一个串使得这个串是甴所给的串相连接构成,连接能够有重叠的部分
首先用所给的串建立自己主动机,每一个单词节点记录当前节点可以达到的最长后缀
開始的时候想的是dp[i][j]表示长度为i,走到自己主动机的j节点的***
可是显然既然是能够反复覆盖的,那么每个节点的dp值都并非最优的由于能够从一个地方截断去连接另外一个串。
所以正确姿势就是dp [i] [j] [k] 表示构造到了长度为 i 的串 如今这个串后面有k 个字符是没有找到有效的节点的,然后在自己主动机上走到了j
那么转移的时候,就有两种情况
为什么是k+1 由于我们如今是去找的儿子节点,已经加1了这种话就是这个節点能够全然覆盖没有匹配到的k个。换句话说就是让后面的k个字符找到了合法节点去匹配那么就转移到dp [i+1] [j->next] [0]...