gistfile1.hs

module std.kmp;

export kmp;

kmpl<a> :: Array<a> -> Array<a> -> Maybe<Int>;
kmp<a> :: Array<a>, Array<a> -> Maybe<Int>;

kmpAdvanceTable<a> :: Array<a> -> Array<Int>;

kmpl(pattern) {
  advanceTable = kmpAdvanceTable(pattern);
  return \(source) {
    m = 0 :: Int;
    i = 0 :: Int;
    while m + i < len(source) {
      if (pattern!!i == source!!(m + i)) {
        if i == len(pattern) - 1 {
          return Just(m);
        } else {
          i = i + 1;
        }
      } else {
        m = m + i - advanceTable!!i;
        if advanceTable!!i > -1 {
          i = advanceTable!!i;
        } else {
          i = 0;
        }
      }
    }
    return Nothing;
  }
}

kmp(pattern, source) := 
  kmpl(pattern)(source);

kmpAdvanceTable(pattern) {
  pos = 2 :: Int;
  cnd = 0 :: Int;
  advanceTable = [ -1, 0 ] :: Array<Int>;
  while pos < len(pattern) {
    if pattern!!(pos - 1) == pattern!!cnd {
      cnd = cnd + 1;
      advanceTable = advanceTable : [cnd];
      pos = pos + 1;
    } elseif cnd > 0 {
      cnd = advanceTable!!cnd;
    } else {
      advanceTable = advanceTable : [0];
      pos = pos + 1;
    }
  }
  return advanceTable;
}