Chinaunix首页 | 论坛 | 博客
  • 博客访问: 346525
  • 博文数量: 105
  • 博客积分: 2730
  • 博客等级: 少校
  • 技术积分: 1110
  • 用 户 组: 普通用户
  • 注册时间: 2007-04-20 12:09
文章分类

全部博文(105)

文章存档

2013年(3)

2012年(2)

2011年(36)

2010年(34)

2009年(6)

2008年(20)

2007年(4)

分类:

2011-03-25 12:16:59

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) |
给主人留下些什么吧!~~