Daily Archives

One Article

信息学奥林匹克竞赛

LibreOJ#3049. 「十二省联考 2019」字符串问题 – 题解

Posted by kal0rona on

主要思路

这个题读完之后大概能知道是要建一个反串的 SAM,然后通过倍增定位 \(A, B\) 串然后加边,找最长路即可。

但是发现直接这样做,碰到 \(|A| < |B|\) 的时候会 GG,因为可能会出现在同一个节点上。这个时候我们就通过长度进行排序,给被重复的节点多做几个影子节点即可。