CF1437G Death DBMS

CF1437G Death DBMS(AC自动机+树剖)

修改就是直接在建出来的 Fail 树上的对应 (endpos) 处修改(对应后文的单点修)。

重点是询问,考虑这个询问对应到 AC 自动机上面是什么:当前串的子串--->当前串每一个前缀的 Fail 树上的祖先。

也就是说就是询问一个点到根的路径上的最大值,直接树剖即可。

原文地址:https://www.cnblogs.com/Akmaey/p/14678491.html