"Berechnung der N-Boxes"

Definition: Eine N-box N[pos] beinhaltet die längste Zeichenkette, die eine Kopie eines Suffix des Suchmusters ist und an der Position pos endet.
Die Definition ist somit völlig analog zu der der Z-box. Ebenso arbeitet der Z-Algorithmus analog zum N-Algorithmus.

Der Algorithmus zur Berechnung der N-boxes untersucht von rechts beginnend Zeichen für Zeichen, ob an der aktuellen Position pos eine Kopie eines Suffix des Suchmusters endet. Ist dies der Fall, haben wir eine N-box gefunden. Dann wird an der Stelle pos - 1 weiterverglichen. Die N-box, die am weitesten nach links reicht wird an ihrer linken Seite mit einem ´l´ und an ihrer rechten Seite mit einem ´r´ markiert.
Bei der Berechnung können nun drei verschiedene Fälle auftreten:

Fall 1: Wir befinden uns in keiner N-box, also: pos < l

Wir müssen Zeichen für Zeichen mit dem Suffix des Suchmusters vergleichen.

Fall 2a: Wir befinden uns in einer N-box, also: pos >= l. Und N[pos´] < pos - l + 1

Da wir uns in einer bereits gefundenen N-box (alpha) befinden und somit in einer Kopie eines Suffix des Suchmusters, können wir einfach die Informationen nutzen, die wir dort schon gewonnen haben. Finden wir zum Beispiel an der pos entsprechenden Stelle pos´ eine N-box (beta), so können wir dieses Wissen ohne jeden weiteren Vergleich übernehmen, wenn beta nicht über l hinausgeht.

Fall 2b: Wir befinden uns in einer N-box, also: pos >= l. Und N[pos´] >= pos - l + 1

Wenn die selben Bedingungen vorliegen wie im Fall 2a, beta jedoch über alpha hinausragt, dann müssen wir die Zeichen links von l untersuchen, ob sie noch zu beta dazugehören. Innerhalb von alpha sind jedoch keine Vergleiche nötig.

Dadurch, daß der Algorithmus schon gewonnene Informationen nutzt, erreicht er eine Laufzeit in der Größenordnung O(n + 1) = O(n).
Dies wird klar, wenn man zwei Fälle betrachtet:
1. Es werden gar keine N-boxes gefunden. Dann führt der Algorithmus n + 1 Vergleiche durch.
2. Es werden N-boxes gefunden. Dann muß der Algorithmus immer nur Vergleiche durchführen, wenn er links von l arbeitet. Rechts von l sind nur Speicherzugriffe aber keine Vergleiche nötig.

Der Boyer-Moore Algorithmus, der im Folgenden betrachtet wird, benötigt den N-Algorithmus für das Preprocessing.