## 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"
``````