Hier ein einfacher Algorithmus um aus zwei Zeichenketten den längsten gemeinsamen Teilstring zu ermitteln.
- Halbiere den String B (den kürzeren) und prüfe jeden Teilstring auf
Übereinstimmungen in A.
- Wenn es keine Treffer gibt halbiere erneut usw.
- Wenn es Treffer gibt werden die Teilstrings gespeichert (jeweils mit ihrer Position in A und B
- Benachbarte Strings werden "zusammengeklebt".
- Dann noch zeichenweise an Anfang und Ende auf weitere Übereinstimmungen des Teilstrings in A mit B prüfen und diese ggf. mit Anfügen.
- Dann den längsten Treffer auswählen.
Das klappt auch bei längeren Texten in einer akzeptablen Geschwindigkeit.
Zum Vergleich habe ich auch mal die "Holzhammer"-Methode umgesetzt die
über zwei for-Schleifen alle möglichen Teilstrings durchgeht.
Die ist natürlich erwartungsgemäß bei längeren Zeichenketten hoffnungslos überfordert, und braucht dann gerne mal ein paar Sekunden.
<?php
/**
* Die größte Übereinstimmung zweier Strings ermitteln
*
*/
// $b = file_get_contents('a.txt');
// $a = file_get_contents('b.txt');
$a = <<< EOT
Hier wird die größte Übereinstimmung von zwei Strings ermittelt.
Also der längste Teiltring welcher in beiden Zeichenketten identisch vorkommt.
EOT;
$b = <<< EOT
Der längste Teilstring welcher identisch vorkommt wird in zwei Strings ermittelt
um die beste Übereinstimmung zu erhalten.
EOT;
function simtext($a, $b)
{
if (strlen($a)<strlen($b)){
$tmp = $a;
$a = $b;
$b = $tmp;
unset($tmp);
}
$tmp = gimme_some_matches($a, $b);
$tmp = glue_it($tmp);
$tmp = expand_right($tmp, $a, $b);
$tmp = expand_left($tmp, $a, $b);
$best = '';
foreach ($tmp as $s){
if (strlen($s[0])>strlen($best)){
$best = $s[0];
}
}
return $best;
}
function expand_right($arr, $a, $b)
{
$stack = array();
foreach ($arr as $one){
$n_a = strpos($a, $one[0]);
$n_b = strpos($b, $one[0]);
if ($n_a === false || $n_b === false){
die ("NOPE");
}
$pos_a = $n_a + strlen($one[0])+0;
$pos_b = $n_b + strlen($one[0])+0;
while (($char_a = substr($a,$pos_a,1)) &&
($char_b = substr($b,$pos_b,1)) && $char_a == $char_b && $char_a != false){
$pos_a++;
$pos_b++;
}
$one[0] = substr($a, $n_a, ($pos_a-$n_a));
$stack[] = $one;
}
return $stack;
}
function expand_left($arr, $a, $b)
{
$stack = array();
foreach ($arr as $one):
$n_a = strpos($a, $one[0]);
$n_b = strpos($b, $one[0]);
if ($n_a === false || $n_b === false){
die ("NOPE");
}
$pos_a = $n_a-1;
$pos_b = $n_b-1;
while (($char_a = substr($a, $pos_a, 1)) &&
($char_b = substr($b, $pos_b, 1)) &&
$char_a == $char_b && ($pos_a >= 0)):
$pos_a--;
$pos_b--;
endwhile;
$one[0] = substr($a, $pos_a+1, ($n_a-$pos_a+strlen($one[0])-1));
$stack[] = $one;
endforeach;
return $stack;
}
function glue_it($arr)
{
$tmp = array();
$nbr = count($arr);
$n = 1;
$current = 0;
while ($current < ($nbr) && $n < $nbr){
if ($arr[$current][1] + strlen($arr[$current][0]) == $arr[$n][1]){
$arr[$current][0] .= $arr[$n][0];
unset($arr[$n]);
$n++;
}else{
$current++;
$n = $current+1;
}
}
return $arr;
}
function gimme_some_matches($a, $b)
{
$l = floor(strlen($b)/2);
$hit = false;
$hits = array();
while (!$hit && $l > 1 ):
$tmp = split_string($b, $l);
foreach ($tmp as $s):
if (($n = strpos($a, $s[0])) !== false){
$hit = true;
$hits[] = array($s[0], $n, $s[1]);
}
endforeach;
$l = ceil($l/2);
endwhile;
return $hits;
}
function split_string($s, $len = 1)
{
$tmp = array();
$l = strlen($s);
for ($i = 0; $i < $l; $i += $len){
$tmp[] = array(substr($s, $i, $len), intval($i));
}
if (($l % $len) != 0){
array_pop($tmp);
}
return $tmp;
}
function holzhammer($a, $b)
{
if (strlen($a)<strlen($b)):
$tmp = $a;
$a = $b;
$b = $tmp;
unset($tmp);
endif;
$stack = array();
$a_len = strlen($a);
$b_len = strlen($b);
$pos = 0;
$hit_len = 0;
for ($pos = 0; $pos < $b_len;$pos++):
for ($i = $b_len;$i > $pos; $i--):
$c_len = $i - $pos;
if ($c_len < $hit_len):
continue;
endif;
$cmp = substr($b, $pos, ($c_len));
if (($n = strpos($a, $cmp)) !== false):
$hit_len = max(strlen($cmp), $hit_len);
$stack[] = $cmp;
endif;
endfor;
endfor;
$best = '';
foreach ($stack as $s):
if (strlen($s)>strlen($best)):
$best = $s;
endif;
endforeach;
return $best;
}
$c = simtext($a, $b);
echo $c;
echo '<hr>';
// Zum Vergleich die Holzhammer-Methode
$c = holzhammer($a,$b);
echo $c;
?>
