自适应朴素字符串匹配

· · 算法·理论

也叫做 carry 字符串匹配。

只是一个在大数据里亚线性被 KMP 完爆的垃圾算法啦。

某一天，弱小的 carryfish 在做某 CSP-S 初赛模拟，然后看到了一个朴素字符串匹配算法，然后他视力非常好，把匹配方向看反了，看成了从后往前比较。

然后他突然发现，如果从后往前匹配的话，是不是可以卡掉传统的：

A=aaab
B=aaaaaaaaaaaab

卡法？

但是显然，如果把 b 放在最前面，同样能卡。

于是 carryfish 想到了一种类似鸡尾酒排序的东西：先比较第一位，再比较最后一位，再比较第二位……依次类推。

但是 b 放中间就又卡掉了。

于是 carryfish 非常红温，他决定每次随机选一个没比较过的位置比较！方式就是通过一个预处理的 opt 数组，opt 数组记录的是每次比较该比较哪个位置，处理方式就是通过 n 轮随机交换 opt 里的两个数完成 opt 的随机打乱。

但是他发现：这样还是类似 O(n) 的复杂度，只是多了一个二分之一的常数……

于是他接着优化，他突然想到：欸，我先比较那个 b 的位置不行吗？于是这个糖糖算法的第一个要点来了：我们有一个 lst 变量，记录上一次失配的位置，下次匹配的时候，我们先匹配这个位置。

突然，这个算法跑很多东西都快了很多。

但是还有一个很容易想到的优化：比较当前匹配窗口的每种字符出现次数，然后我们看看是否有任何一种不同，不同就直接 continue，这个优化复杂度是 O(1) 的，但又能优化掉很多东西。

突然，carryfish 发现，虽然这种算法在 m 很小的时候很容易达到 O(nm)，但是在 m 比较大的时候突然就卡不住了。

介于这太诡异了，所以想要来找找 Hack，不过貌似确实是个很神奇的朴素暴力优化算法？