Re: [問題] 二維的字串比對問題
看板Prob_Solve (計算數學 Problem Solving)作者yalight (ㄚ光)時間18年前 (2006/07/07 12:20)推噓0(0推 0噓 1→)留言1則, 1人參與討論串4/9 (看更多)
※ 引述《windows2k (KERORO軍曹)》之銘言：
: 傳統的一維比對, 給定一個字串 text 和一個 pattern
: 要看看pattern是否有在 text出現過
: 對於這種問題, 已經有很多解決方案, 如 BM, KMP之類的演算法
: 那如果變成二維的情況該怎麼轉化成一維
: 如
: abc bc
: bcd 中要找出 cd 這個pattern
: cde
: 可以找到
: abc abc
: bcd 和 bcd
: cde cde
: 兩組解
: 該怎麼把二維的問題轉成一維來做?
不知道可不可以把它都接成一串 ^^?
然後用 KMP 做, jump table(fail link) 要改
在搜尋的時候也要跳...
蠻煩的 XD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.205.19
※ 編輯: yalight 來自: 140.115.205.19 (07/07 12:38)
→
07/07 12:41, , 1F
07/07 12:41, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 9 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
