Re: [問題] 二維的字串比對問題
看板Prob_Solve (計算數學 Problem Solving)作者yalight (ㄚ光)時間18年前 (2006/07/07 13:03)推噓1(1推 0噓 0→)留言1則, 1人參與討論串6/9 (看更多)
※ 引述《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)
推
07/07 13:23, , 1F
07/07 13:23, 1F
※ 編輯: yalight 來自: 140.115.205.19 (07/07 14:27)
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 6 之 9 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
