作者ledia (contemplation)
站内Prob_Solve
标题Re: [问题] 二维的字串比对问题
时间Fri Jul 7 14:31:17 2006
※ 引述《ledia (contemplation)》之铭言：
: 初步想法是先一个 row 一个 row 看
: 采用 multi-pattern search
: 现在是一个 column 一个 column 看
: 看看是否有 1~n (这里是 1-2) 的连续字串
: 也就是 "12"
: 这里再用 single pattern search
: 就可以找到所有的 occurence
1F：推 yalight:这样要 O(mn(m+n)), m,n 分别是 text 和 pattern 的行数 07/07 12:47
2F：推 yalight:比暴力法 O(m^2n^2) 好一点 ^^ 07/07 12:51
假设 grid 是 nxn, pattern 长度总和是 m
第一个步骤, multi-pattern search
以 Aho/Corasick 来说, 一次需时 O(m+n)
time complexity 是 O(n(m+n))
第二个步骤, single pattern search
因为 pattern 固定为 size n
以任何 linear time algorithm 应该是 O(n+n^2)
--
有时候，遗忘，是令人快乐的。什麽时候？当然是有人伤了你的心的时候。
存心伤你的那个人，固然是故意和你过不去，但是被伤了心而耿耿於怀的你
，却是和自己过不去了。所以，记性不好的人，通常会是比较快乐的人，也
是比较不容易被击倒的人。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.30.56
※ 编辑: ledia 来自: 140.112.30.56 (07/07 14:32)