※ 引述《windows2k (KERORO军曹)》之铭言： : 传统的一维比对, 给定一个字串 text 和一个 pattern : 要看看pattern是否有在 text出现过 : 对於这种问题, 已经有很多解决方案, 如 BM, KMP之类的演算法 : 那如果变成二维的情况该怎麽转化成一维 : 如 : abc bc : bcd 中要找出 cd 这个pattern : cde : 可以找到 : abc abc : bcd 和 bcd : cde cde : 两组解 : 该怎麽把二维的问题转成一维来做? 初步想法是先一个 row 一个 row 看 采用 multi-pattern search 然後抓 abc 来看, 可以知道 match bc abc 010 <-- 1 means match 第一组, 0 means no match 接着抓 bcd 来看, 可以知道 match bc, cd bcd 120 最後看 cde cde 200 把 match map 合起来 abc 010 bcd => 120 cde 200 现在是一个 column 一个 column 看 看看是否有 1~n (这里是 1-2) 的连续字串 也就是 "12" 这里再用 single pattern search 就可以找到所有的 occurence -- 有时候，遗忘，是令人快乐的。什麽时候？当然是有人伤了你的心的时候。 　存心伤你的那个人，固然是故意和你过不去，但是被伤了心而耿耿於怀的你 　，却是和自己过不去了。所以，记性不好的人，通常会是比较快乐的人，也 　是比较不容易被击倒的人。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.56 ※ 编辑: ledia 来自: 140.112.30.56 (07/07 11:24)