Re: [問題] 二維的字串比對問題
看板Prob_Solve (計算數學 Problem Solving)作者ledia (contemplation)時間18年前 (2006/07/07 14:26)推噓0(0推 0噓 0→)留言0則, 0人參與討論串7/9 (看更多)
※ 引述《ledia (contemplation)》之銘言：
: 初步想法是先一個 row 一個 row 看
: 採用 multi-pattern search
: 現在是一個 column 一個 column 看
: 看看是否有 1~n (這裡是 1-2) 的連續字串
: 也就是 "12"
: 這裡再用 single pattern search
: 就可以找到所有的 occurence
推
07/07 12:47,
07/07 12:47
推
07/07 12:51,
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)
討論串 (同標題文章)
完整討論串 (本文為第 7 之 9 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
