又是一道明明很明晰却困了我一个上午的题。完了我刷蓝书的进度要被吊打了
解一 字符串Hash结合二分
$\mathrm{O}(n+m)$预处理出两个字符串的前缀哈希。对于每一个$S$的后缀$suf(i)$，设其与$T$的最大匹配长度为$maxl(i)$。容易发现二者前缀哈希是否相等具有单调性。$\mathrm{O}(\log n)$二分每个后缀的答案，最后统计每种$maxl$的计数即可。代码实现略。
其实昨晚扫一眼题就想到了这个做法。要不是愣是要研究KMP，也不至于沦落到如此地步（
标签： 字符串匹配
-
AcWing 160 匹配统计 – 题解与思路重现