UVA11019 Matrix Matcher

UVA11019 Matrix Matcher

题意:

给定两个字符矩阵 (A)(B) ,求 (A) 中有多少个子矩阵和 (B) 完全相同。

解答:

最开始毫无思路,但是我们可以根据 “二维字符矩阵匹配” 转化成 “一维字符串匹配”。

于是我们可以想到先将 (A)(B) 的每一行都缩成一个字符串(去重),然后我们可以对 (B) 的所有串建立一个 (AC) 自动机,把 (A) 的每一个串放进去匹配。

对于一个字符串 (A_i) 来说,我们假设它在位置 (j) 开始匹配到了 (B_k) ,那么我们就把对应点 ((i,j)) 的编号设为 (k)

接下来相当于我们已经处理掉了横着的一维,对于列的一维,我们先将原 (B) 矩阵看成一个一维的编号数组。

然后我们对于 (A) 矩阵的每一列匹配这个一维编号数组就行了,实际上就是 KMP 匹配两个字符串即可。

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