Friday, November 2, 2012

F# on Algorithm - String KMP Algorithm

the KMP algorithm is used for string matching. The algorithm is listed below.

 type List = System.Collections.Generic.List<int>  
 let kmp ( w: string ) =   
   let t = List([1..w.Length])  
   let mutable pos = 2  
   let mutable cnd = 0  
   t.[0] <- -1  
   t.[1] <- 0  
   while pos < w.Length do  
     if w.[pos-1] = w.[cnd] then  
       cnd <- cnd + 1  
       t.[pos] <- cnd  
       pos <- pos + 1  
     elif cnd>0 then  
       cnd <- t.[cnd]  
     else  
       t.[pos] <- 0  
       pos <- pos + 1  
   t |> List.ofSeq  
 type ResultType =   
   { mutable Result : int; mutable Found : bool }  
     with  
       member this.SetFound(b) = this.Found <- b  
       member this.SetResult(c)= this.Result<- c  
       static member InitialValue = { Result = -1; Found=false }  
 let kmpSearch (s:string) (w:string) : int =   
   let mutable m = 0  
   let mutable i = 0  
   let t = kmp w  
   let v = ResultType.InitialValue  
   while (i+m) < s.Length && not v.Found do  
     if w.[i] = s.[m+i] then  
       if i = w.Length - 1 then  
         v.SetFound true  
         v.SetResult m  
       i <- i + 1  
     else  
       m <- m + i + t.[i]  
       i <- if t.[i] > -1 then t.[i] else 0  
   v.Result  
 let s = "ABCABCDABABCDABCDABDE"  
 kmpSearch s "ABCDABD"  

No comments: