针对多模式串问题的广义SAM不是有一种盗版写法嘛?
对于每个模式串,把 last 设为 1,然后像普通 SAM 那样插入。
这样显然不够侑秀,一个等价类被拆成了若干个节点,子串信息被分散。
但这个自动姬依旧存在正确性,且复杂度依旧为线性。
那么问题来了,之前的我一直无条件相信了这篇博客里的东西,被误导了很多东西(包括在线构造的写法、复杂度等等),以为只要 跑匹配 或者 维护了pos(在insert时维护前缀串在SAM上的等价类节点位置)、siz(节点endpos大小)就会被卡。
但事实上被卡的原因在于pos数组映射到了空节点z上面,只要注意调整 pos 数组的映射,正确性显然,匹配时也不会出锅(只是拆开了等价类,并不会出现两个等价类维护同一子串的情况),而且复杂度似乎也没有问题(还是线性)
......所以这个东西到底有没有办法卡掉啊(正确性/复杂度均可)