Skip to content
Fetching contributors…
Cannot retrieve contributors at this time
165 lines (130 sloc) 3.63 KB
/* ------------------------------------------------------------------------- */
/* Shift-Or exact string matching algorithm */
/* */
/* See ESMAJ: http://www-igm.univ-mlv.fr/~lecroq/string/node6.html */
/* ------------------------------------------------------------------------- */
/* NOTE: there's a bug in this program but I was too lazy to fix it ;) (P.) */
using Nemerle.IO;
using System;
using System.Collections;
class ShiftOr
{
private mutable _pattern : array [char];
private mutable _pattern_length : int;
private mutable _R : BitArray;
private mutable _S : array [BitArray];
private mutable _L : BitArray;
private shift_left (mask : BitArray) : void
{
def shift (index) {
when (index >= 0) {
mask.Set (index + 1, mask.Get (index));
mask.Set (index, false);
shift (index - 1)
}
};
shift (mask.Length - 2)
}
private shift_right (mask : BitArray) : void
{
def shift (index : int) : void {
when (index < mask.Length) {
mask.Set (index - 1, mask.Get (index));
mask.Set (index, false);
shift (index + 1)
}
};
shift (1)
}
private init_S (index : int) : void
{
when (index < 256)
{
_S [index] = BitArray (_pattern_length, true);
init_S (index + 1)
}
}
private build_S (index : int) : void
{
when (index < _pattern_length)
{
assert((_pattern [index] :> int) < 256,
"only 8-bit wide characters are allowed for simplicity");
mutable mask = BitArray (_pattern_length, true);
mask.Set (index, false);
def current_char = (_pattern [ index ] :> int);
def s = _S [ current_char ];
_S [ current_char ] = s.And (mask);
mask = mask.Not ();
_L = _L.Or (mask);
build_S (index + 1)
}
}
#if DEBUG
private static dump (title : string, mask : BitArray) : void
{
printf ("(%s):%d: ", title, mask.Length);
def loop (index : int) : void {
when (index >= 0) {
printf ("%s", if (mask.Get (index)) "!" else ".");
loop (index - 1);
}
};
loop (mask.Length - 1);
printf ("\n")
}
#endif
public this (pattern : string)
{
_pattern = pattern.ToCharArray ();
_pattern_length = pattern.Length;
_L = BitArray (_pattern_length, false);
_S = array (256);
init_S (0);
build_S (0);
shift_right (_L);
_L = _L.Not ()
}
public Search (text : string) : option [int]
{
_R = BitArray (_pattern_length, true);
def text = text.ToCharArray ();
def le (index : int, l : BitArray, r : BitArray) : bool
{
if (index > 0) {
if (l.Get (index) == false && r.Get (index) == true)
true
else
le (index - 1, l, r)
}
else false
};
def loop (index)
{
if (index < text.Length) {
shift_left (_R);
def t = _S [ (text [ index ] :> int) ];
_R = _R.Or (t);
if (le (_R.Length - 1, _R, _L))
Some (index)
else
loop (index + 1)
}
else None ();
};
loop (0)
}
public static Main () : void
{
def r = ShiftOr ("coca");
match (r.Search ("Trink coca cola!")) {
| Some (i) => printf ("Found, ending at index %d\n", i + 1)
| None => printf ("Not found\n")
}
}
}
/*
BEGIN-OUTPUT
Found, ending at index 10
END-OUTPUT
*/
Something went wrong with that request. Please try again.