Re: [問題] 二維的字串比對問題
看板Prob_Solve (計算數學 Problem Solving)作者ledia (contemplation)時間18年前 (2006/07/07 11:20)推噓2(2推 0噓 0→)留言2則, 1人參與討論串2/9 (看更多)
※ 引述《windows2k (KERORO軍曹)》之銘言：
: 傳統的一維比對, 給定一個字串 text 和一個 pattern
: 要看看pattern是否有在 text出現過
: 對於這種問題, 已經有很多解決方案, 如 BM, KMP之類的演算法
: 那如果變成二維的情況該怎麼轉化成一維
: 如
: abc bc
: bcd 中要找出 cd 這個pattern
: cde
: 可以找到
: abc abc
: bcd 和 bcd
: cde cde
: 兩組解
: 該怎麼把二維的問題轉成一維來做?
初步想法是先一個 row 一個 row 看
採用 multi-pattern search
然後抓 abc 來看, 可以知道 match bc
abc
010 <-- 1 means match 第一組, 0 means no match
接著抓 bcd 來看, 可以知道 match bc, cd
bcd
120
最後看 cde
cde
200
把 match map 合起來
abc 010
bcd => 120
cde 200
現在是一個 column 一個 column 看
看看是否有 1~n (這裡是 1-2) 的連續字串
也就是 "12"
這裡再用 single pattern search
就可以找到所有的 occurence
--
有時候，遺忘，是令人快樂的。什麼時候？當然是有人傷了你的心的時候。
存心傷你的那個人，固然是故意和你過不去，但是被傷了心而耿耿於懷的你
，卻是和自己過不去了。所以，記性不好的人，通常會是比較快樂的人，也
是比較不容易被擊倒的人。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.56
※ 編輯: ledia 來自: 140.112.30.56 (07/07 11:24)
推
07/07 12:47, , 1F
07/07 12:47, 1F
推
07/07 12:51, , 2F
07/07 12:51, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 9 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
