import Data.Array (listArray, (!))
kmpMatcher :: String -> String -> (Int,Int)
kmpMatcher b p = kmpIter 0 0 [(0,0)]
where
-- prefix tabel
pt = listArray (0, (pl)) (prefixGen p)
-- base (long) array
bl = length b
ba = listArray (0,(bl - 1)) b
-- pattern (short) array
pl = length p
pa = listArray (0,(pl - 1)) p
kmpIter bi pi debug =
if pi >= pl -- pattern matched
then (bi-pl+1,bi) --((bi,pi):debug)
--then True
else
if bi >= bl -- no more chance
then (-1,-1) --((bi,pi):debug)
--then False
else
if (ba ! bi) == (pa ! pi) -- match
then kmpIter (bi + 1) (pi + 1) (((bi + 1),(pi + 1)):debug)
else
if pi == 0 -- need or not to look up
then kmpIter (bi + 1) 0 ((bi+1,0):debug)
else kmpIter (bi) (pt ! pi) ((bi,(pt ! pi)):debug)
prefixGen :: String -> [Int]
prefixGen s@(x:xs) = iter xs 0 [0,0]
where
len = length s
ay = listArray (0,(len-1)) s
iter :: String -> Int -> [Int] -> [Int]
iter (y:ys) pl rs =
if y == (ay ! (pl))
then iter ys (pl+1) ((pl+1):rs)
else iter ys 0 (0:rs)
iter [] pl rs = reverse rs
阅读(610) | 评论(0) | 转发(0) |