/* ------------------------------------------------------------------------- */
/*   Knuth-Morris-Pratt exact string matching algorithm                      */
/*                                                                           */
/*   See ESMAJ: http://www-igm.univ-mlv.fr/~lecroq/string/node8.html         */
/* ------------------------------------------------------------------------- */

using System.Array;
using Nemerle.IO;

class PrefixFunction
{
  private mutable _prefix_function : array [int];
  private mutable _pattern : array [char];
  private mutable _pattern_length : int;

  public this (pattern : string)
  {
    _pattern = pattern.ToCharArray ();
    _pattern_length = pattern.Length;

    _prefix_function = array (_pattern_length + 1);

    calculate_prefix_function ()  
  }

  public Get (index : int) : int 
  {
    _prefix_function [index]
  }

  private calculate_prefix_function () : void 
  {
    mutable i = 0;
    mutable j = -1;
    
    _prefix_function [0] = -1;
    
    while (i < _pattern_length) {
      while (j > -1 && _pattern [i] != _pattern [j]) {
        j = _prefix_function [j]
      };
      
      i = i + 1;
      j = j + 1;
      
      if (i < _pattern_length && _pattern [i] == _pattern [j])
        _prefix_function [i] = _prefix_function [j]
      else
        _prefix_function [i] = j
    }
  }
}


class KMP
{
  private mutable _pattern : array [char];
  private mutable _pattern_length : int;

  private mutable _prefix_function : PrefixFunction;

  public this (pattern : string) 
  {
    _pattern = pattern.ToCharArray ();
    _pattern_length = pattern.Length;

    _prefix_function = PrefixFunction (pattern)
  }


  public Search (text : string) : option [int] 
  {
    def text_length = text.Length;
    def text = text.ToCharArray ();
    
    mutable i = 0;
    mutable j = 0;
    
    def search_loop () : option [int] 
    {  
      if (j < text_length) 
      {
        while (i > -1 && _pattern [i] != text [j]) {
          i = _prefix_function.Get (i)
        };

        i = i + 1;
        j = j + 1;

        if (i >= _pattern_length)
          Some (j - i)
        else
          search_loop () 
      }
      else None ()
    };
    
    search_loop ()
  }

  
  public static Main () : void 
  {
    def r = KMP ("ziemi egipskiej");
    
    match (r.Search ("Jam jest Pan Bóg twój, który Cię wywiódł z ziemi egipskiej, z domu niewoli")) {
      | Some (i) => printf ("Found at position %d\n", i + 1)
      | None => printf ("Not found\n")
    }
  }
}

/*
BEGIN-OUTPUT
Found at position 44
END-OUTPUT
*/