标签： next数组

AcWing 159 – 奶牛矩阵

这道题的题意让我们想起了最小循环节。我们先不考虑这个矩阵的具体位置。由题可知，只要扩展的矩阵覆盖原矩阵即可。考虑以下图形：

黑线为原矩阵。红线是一种最小子矩阵的划分。请看绿色和蓝色矩形，它们分别是没有占够一整个矩形宽度的左右边界，以及对应到每个完整的子矩形中的位置。如果我们以灰线为界，将最小子矩形平移至与灰线之间对齐，则最小子矩形的扩展就从原矩形的最左端开始。上下两端的处理同理。这与之前的划分显然是等价的。因此，我们可以只考虑从左端、顶端开始的子矩阵的划分。

（更多…）

160. 匹配统计 – AcWing题库

又是一道明明很明晰却困了我一个上午的题。完了我刷蓝书的进度要被吊打了

解一 字符串Hash结合二分

$\mathrm{O}(n+m)$预处理出两个字符串的前缀哈希。对于每一个$S$的后缀$suf(i)$，设其与$T$的最大匹配长度为$maxl(i)$。容易发现二者前缀哈希是否相等具有单调性。$\mathrm{O}(\log n)$二分每个后缀的答案，最后统计每种$maxl$的计数即可。代码实现略。

其实昨晚扫一眼题就想到了这个做法。要不是愣是要研究KMP，也不至于沦落到如此地步（

解二 KMP模式匹配与next数组

（更多…）