作者yalight (ㄚ光)
站内Prob_Solve
标题Re: [问题] 二维的字串比对问题
时间Fri Jul 7 13:13:55 2006
※ 引述《windows2k (KERORO军曹)》之铭言：
: 传统的一维比对, 给定一个字串 text 和一个 pattern
: 要看看pattern是否有在 text出现过
: 对於这种问题, 已经有很多解决方案, 如 BM, KMP之类的演算法
: 那如果变成二维的情况该怎麽转化成一维
: 如
: abc bc
: bcd 中要找出 cd 这个pattern
: cde
: 可以找到
: abc abc
: bcd 和 bcd
: cde cde
: 两组解
: 该怎麽把二维的问题转成一维来做?
abc ab bc
把 bcd 拆成 bc , cd 就是跟 pattern 一样的宽度
cde cd de
然後分别从里面找, 要比对 m-n 个,
ab A
然後把 bc 编成 B 之类的, 还是用 Huffman code @_@"
cd C
bc B
pattern cd 就编成 C, 然後就是 ABC 和 BC 做一维的比对噜~@_@"
m, n 分别是 text 和 pattern 的宽度
复杂度 O( (m-n)*( m+n + [编码(m+n)个字串] ))
^^^
如果分别是 m 列和 n 列
= O( (m^2-n^2) + [编码(m+n)个字串]*(m-n) )
= O( (m^2-n^2) + k(m+n)(m-n) ) = O(m^2-n^2)
感觉起来好像非常好 @@"
比接成一串的 KMP O(m^2+n^2) 好
不知道有没有算错 Orz...
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.115.205.19
※ 编辑: yalight 来自: 140.115.205.19 (07/07 13:20)
※ 编辑: yalight 来自: 140.115.205.19 (07/07 13:22)
※ 编辑: yalight 来自: 140.115.205.19 (07/07 13:23)
1F：推 pause2:pattern间的长度若不一样,就要对每种pattern长度做一样的事 07/07 13:23
※ 编辑: yalight 来自: 140.115.205.19 (07/07 14:27)