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

Zur Erinnerung noch einmal die Definition von L'[pos]:

L'[pos] := Das rechte Ende der rechtesten Kopie von Muster[pos..n].

Der Algorithmus, der das Array L'[] berechnet bedient sich der N-boxes, die vorher für das Suchmuster berechnet wurden. Hierbei werden zuerst alle Werte in L'[] auf '0' gesetzt, dann durchläuft der Algorithmus das Array der N-Boxes. Trifft er auf eine N-Box, die größer als Null ist, so projeziert man deren Länge auf das Ende des Suchmusters und erhält dadurch das Suffix Muster[pos..n], das an der Stelle nochmal im Suchmuster vorkommt, die von der N-box umschlossen wird. Mit 'j' als rechtem Ende dieser N-box ergibt sich im L'-Array also der Eintrag L'[pos] := j.
Da das Array der N-boxes von links ('0') nach rechts ('n - 1') durchlaufen wird, steht nach Terminierung des Algorithmus immer das rechteste nochmalige Vorkommen eines Suffix in L'[].
Wenn eine N-box die Länge '0' hat wird in L'[] nichts verändert.

L'-Algorithmus

Der Algorithmus schaut formal notiert so aus:


for pos := 1 to n do L'[pos] := 0; // Initialisierung mit '0'
for j := 0 to n - 1 do
    begin
    pos := n - N[j] + 1;
    L'[pos] := j;
    end;


Da die for-Schleife genau n mal durchlaufen wird, läuft der Algorithmus in linearer Zeit ab.
Die nächste Folie behandelt dann die Berechnung des Arrays l'[].


Vorherige Folie Zurück zum Index Nächste Folie