※ 引述《windows2k (KERORO军曹)》之铭言： : 传统的一维比对, 给定一个字串 text 和一个 pattern : 要看看pattern是否有在 text出现过 : 对於这种问题, 已经有很多解决方案, 如 BM, KMP之类的演算法 : 那如果变成二维的情况该怎麽转化成一维 : 如 : abc bc : bcd 中要找出 cd 这个pattern : cde : 可以找到 : abc abc : bcd 和 bcd : cde cde : 两组解 : 该怎麽把二维的问题转成一维来做? 你所提的应该是所谓的 "multiple pattern matching" 的问题 比较着名的有 Aho-Corasick, Wu-Manber等algorithm 我简述一下 Aho-Corasick algorithm 的作法 它是把多个 pattern 建成 finite-state-machine， 以你提的例子，有个initial state 0，吃到 b 进到 state 1 state 1 吃到 c 进到 state2 , state2为一个final state~ 表示中了pattern "bc" 以此类推~ 然後把input text一个个的放入 state-machine里run 则对每个text，在 O(len(text)) 内，知道有没有中哪个pattern~ search时间与pattern的多寡无关，只与text长度有关 关於 pattern-matching 的问题，还有很多的演算法，可以查查~ --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 218.168.174.44 ※ 编辑: pause2 来自: 218.168.174.44 (07/07 12:21)