|
Knuth-Morris-Pratt Algorithm
enter your pattern and string and press the send-button.
you will get the next-Array and it will check if the pattern was found in the string.
(this won't work on NS! I hate NS for that!!! If you use that dumb browser that's your own problem!)
©2001 Philip Iezzi
|
|
pattern [10100111] found in string:
position 16
100111010010100010100111000111 |
here's the PHP-code I used:
<?php
/*--------------------------------------------
Knuth-Morris-Pratt Algorithm
function to initialize next-Array
(c) Philip Iezzi <www.iezzi.ch> 2001-02-06
-------------------------------------------- */
function initnext($p) {
$m = strlen($p);
$i = 0; $j = -1; $next[0] = -1;
while($i < $m) {
if (($j == -1) || (substr($p,$i,1) == substr($p,$j,1))) {
$i += 1;
$j += 1;
$next[$i] = $j;
} else {
$j = $next[$j];
}
}
return $next;
}
/*--------------------------------------------
Knuth-Morris-Pratt Algorithm
find pattern $p in string $s
(c) Philip Iezzi <www.iezzi.ch> 2001-02-06
-------------------------------------------- */
function kmpSearch ($s,$p) {
global $next;
$m = strlen($s); // length of string (index i)
$n = strlen($p); // length of pattern (index j)
for ($i=0,$j=0; $i < $m & $j < $n; $i++,$j++)
while (($j >= 0) && (substr($s,$i,1) != substr($p,$j,1)))
$j = $next[$j];
if ($j == $n) return $i-$n;
else return false;
}
?>
|
>>>
ALGOPHORUM <<< - NEW!!! Algodat discussion
forum
|
