题解 P5284 【[十二省联考2019]字符串问题】

思博题，模拟题意就行了，然而毒瘤出题人卡常数。。。（多测什么鬼啊） 考虑模拟题意： 显然你是要把 $A_x \to B_y$，在这 $m$ 条限制下 然后如果 $B_x$ 是 $A_y$ 的前缀的话，连接一条 $B_x \to A_y$ 的边 之后跑最长路就是答案咯，注意判断是否有环 那么如何通过 $100pts$ 呢？ 昨天刚刚学习了一波 $sam$，那么遇到这种又是子串又是 $lcp$ 肯定就是 $sam$ 之类的玩意套一套了 考虑建立反串的 $parent$ 树，那么前缀和优化建图就好了 **注意卡常！！！** **注意卡常！！！** **注意卡常！！！**