"Berechnung von l'[1..n]"

Die Definition von l'[pos] lautete folgendermaßen:

l'[pos] := Länge des längsten Suffix in Muster[pos..n], das auch Präfix ist.

Die Berechnung des Arrays erfolgt auch wieder mit Hilfe der vorher berechneten N-boxes. Man geht das Suchmuster von links aus Zeichen für Zeichen durch und prüft, ob an der aktuellen Position eine N-box endet, die ganz am Anfang des Suchmusters beginnt, also ein Präfix ist. Da eine N-box ja eine Kopie eines Suffix des Suchmusters ist, haben wir dann für den entsprechenden Bereich das größte Präfix gefunden, das gleichzeitig auch ein Suffix ist. Und dies gilt solange, bis ein noch größeres gefunden wird.

l'-Algorithmus

Der Algorithmus formal notiert:

temp := 0; for pos := 0 to n - 1 do
    begin
    if N[pos] == pos + 1 then temp := pos + 1;
    l'[n - pos] := temp;
    end;

Auch hier gilt wieder: Der Algorithmus arbeitet in linearer Zeit, weil die for-Schleife genau n mal durchlaufen wird.

Zum Abschluß empfiehlt es sich, nochmal die Übersicht zum Boyer-Moore Algorithmus anzuschauen da die Zusammenhänge jetzt erst vollständig erkennbar sind.


Vorherige Folie Zurück zum Index Übersicht