討論串(共9篇) - [問題] 二維的字串比對問題 - 看板Prob_Solve

看板 [ Prob_Solve ]

討論串[問題] 二維的字串比對問題

共 9 篇文章

排序：最舊先 | 最新先 | 留言數 | 推文總分

內容預覽：開啟 | 關閉 | 只限未讀

首頁

尾頁

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

推噓0(0推 )留言0則，0人參與作者windows2k (KERORO軍曹)時間18年前 (2006/07/07 10:35)資訊

內容預覽:

傳統的一維比對, 給定一個字串 text 和一個 pattern. 要看看pattern是否有在 text出現過. 對於這種問題, 已經有很多解決方案, 如 BM, KMP之類的演算法. 那如果變成二維的情況該怎麼轉化成一維. 如. abc bc. bcd 中要找出 cd 這個pattern. cd

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

推噓2(2推 )留言2則，0人參與作者ledia (contemplation)時間18年前 (2006/07/07 11:20)資訊

內容預覽:

初步想法是先一個 row 一個 row 看. 採用 multi-pattern search. 然後抓 abc 來看, 可以知道 match bc. abc. 010 <-- 1 means match 第一組, 0 means no match. 接著抓 bcd 來看, 可以知道 match bc

(還有276個字)

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

推噓2(2推 )留言2則，0人參與作者pause2 (好大的陽光)時間18年前 (2006/07/07 12:12)資訊

內容預覽:

你所提的應該是所謂的 "multiple pattern matching" 的問題. 比較著名的有 Aho-Corasick, Wu-Manber等algorithm. 我簡述一下 Aho-Corasick algorithm 的作法. 它是把多個 pattern 建成 finite-state-

(還有243個字)

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

推噓0(0推 )留言1則，0人參與作者yalight (ㄚ光)時間18年前 (2006/07/07 12:20)資訊

內容預覽:

不知道可不可以把它都接成一串 ^^?. 然後用 KMP 做, jump table(fail link) 要改. 在搜尋的時候也要跳.... 蠻煩的 XD. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 140.115.205.19. ※ 編輯: yalight 來自: 14

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

推噓2(2推 )留言2則，0人參與作者windows2k (KERORO軍曹)時間18年前 (2006/07/07 12:50)資訊

內容預覽:

如果我沒弄錯你的意思的話. 假設. bcb. cbc 中要找 bc這個 pattern. bcb. 有可能找到. bcb. cbc. bcb. 這組解, 應該有辦法克服, 不過我還沒想到就是了. --. ※ 發信站: 批踢踢實業坊(ptt.cc). ◆ From: 140.115.156.192.

首頁

尾頁