[Algorithm]二维模式（矩阵）匹配（Rabin-Karp算法推广到二维）
October 8, 2010
本文着重讨论由Rabin-Karp算法推广到二维来解决二维模式匹配问题的算法。
问题：
在一个n1*n2的二维字符组成中搜寻一个给定的m1*m2的模式。参考《算法导论》习题32.2-3.
分析：
1. 首先简单介绍一下Rabin-Karp算法
Rabin-Karp算法是一种字符串匹配算法，它的主要思想是预先计算出模式串的hash值，匹配时再计算出待匹配子串的hash值，直接比较模式串和当前子串的hash值是否相等即可判断是否匹配。
为了便于说明，以下以数字串为例（字符串的每个字符都是一个十进制的数字，比如字符串31415）。已知一个模式P[1..m]，设p表示其相应的十进制数的值。类似的，对于[......]
0
(2,864 views)