Re: [問題] 二維的字串比對問題

[ledia (contemplation)]

※ 引述《ledia (contemplation)》之銘言：
:  初步想法是先一個 row 一個 row 看
:  採用 multi-pattern search

:  現在是一個 column 一個 column 看
:  看看是否有 1~n  (這裡是 1-2) 的連續字串
:  也就是 "12"

:  這裡再用 single pattern search
:  就可以找到所有的 occurence

推 yalight:這樣要 O(mn(m+n)), m,n 分別是 text 和 pattern 的行數
推 yalight:比暴力法 O(m^2n^2) 好一點 ^^
  假設 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)