Der Korrektheitsbeweis ist auch nicht schwer. Also hier dieser Satz 14 sagt, dass dieser Algorithmus alle exakten Vorkommen von P in T liefert.
Das Bild ist hier als Kopie. Jetzt machen wir also den ... Beweis.
Es sind zwei Richtungen zu zeigen. Angenommen, Zeile 6 liefert ein Vorkommen und wird ausgeführt, wenn ZI gleich N ist. Wir müssen dann einerseits zeigen, dass wenn ZI gleich n ist, für ein i in diesem Bereich, dann kommt tatsächlich P in T in der Position i minus n minus 1 vor. Also sei n plus 2 kleiner gleich i kleiner gleich m plus 2 und sei ZI gleich n. Gemäß der Konstruktion vom String S  und nach der Definition von dem Z-Wert von S an der Stelle i folgt daraus, dass P gleich S ist von i bis i plus n minus 1.
Jetzt kann man diese Koordinaten umrechnen. Das ist dann also T von i minus n minus 1 bis ... von dieser Koordinate kann ich jetzt einfach noch abziehen: N und 1. Das heißt aber, die Länge hier ist ja N plus 1. Das heißt P kommt in T an der Stelle i  minus n minus 1 vor. Das bedeutet, dass die Ausgaben des Algorithmus tatsächlich richtig sind. Diese Position hier, ist ja das, was der Algorithmus tatsächlich ausgibt.
Machen wir es nun umgekehrt. Angenommen P komme in T vor, sagen wir an der Stelle j. Dann folgt daraus, dass P gleich T j bis j plus n minus 1 gilt.
Das bedeutet jetzt wiederum nach der Konstruktion von S, dass P in S vorkommt an der Stelle S plus n plus 1 bis j plus n minus 1 plus n plus 1.
Und Wir haben jetzt außerdem, dass j plus n plus 1 zwischen diesen beiden Bereichen liegt, kleiner gleich m plus 2.
Und wir haben noch, dass der Z-Wert an der Stelle j plus n plus 1 gleich N ist. Theoretisch könnte das ja auch noch länger matchen, aber weil das Dollarzeichen nicht in T vorkommt --- ich zeichne das gerade mal ein --- die Stelle hier wäre dann bei j. Wir müssen auf jeden Fall hier einen Mismatch haben.
Diese beiden Zeichen können nicht gleich sein, weil das Dollar nicht in T vorkommt. Der Algorithmus gibt dann auch die Position aus.
Dann können wir hier folgern, der Z-Algorithmus gibt also j plus n plus 1 minus n minus 1 gleich j als Vorkommen aus.
Das ist ja einfach nach Konstruktion relativ direkt ersichtlich.

Die Konstruktion sieht zwar ein bisschen künstlich aus, aber wir haben jetzt einen Algorithmus, der uns alle Vorkommen von P in T liefert.
Jetzt kommt noch die Laufzeit. Wir gucken uns das für diesen Pseudocode einfach mal an. Die Behauptung ist, dass der in Zeit O von n plus m läuft.
Dafür muss man sich aber bloß hier den Pseudocode nochmal ansehen. Die Konstruktion von S geht in O von Länge von n plus m, wenn ich die Eingabestring in einen neuen String kopiere.
In der Praxis würde man das vielleicht nicht machen, sondern einfach nur mit der Umrechnung von Indizes arbeiten. Also je nachdem, ob ein Index vor oder nach dem Dollar ist, indiziere ich entsprechend in P oder T. Dann muss ich nicht die Eingaben kopieren und spare neben dem Speichplatz dafür außerdem Zeit.
Ich wende dann den Z-Algorithmus an. Das ist die Hauptarbeit hier. Dann kommt nochmal eine Schleife, die höchstens Oh von m Iterationen hat.
Zeile 5 und 6 haben konstanten Aufwand. Also ergibt sich hier folgende Laufzeit. Wie wir vorher bewiesen über den Z-Algorithmus, haben wir hier eine Laufzeit für die Konstruktion von den Z-Werten von O von Länge von S. Und das ist hier n plus m plus 1. Bei dem Speicherbedarf rechnen wir das, was zusätzlich zur Eingabe noch gespeichert werden muss.
Wenn man ganz naiv rangeht, speichert man ja alle Z-Werte. Dann hat man also Oh von N plus M Speicherbedarf.
Allerdings kann man hier einfach folgendes feststellen. Im Z-Algorithmus ist für jede Position k, das entsprechende k Strich innerhalb einer Z-Box und Z-Boxen können nicht länger sein als n, da ja das Dollar nicht in T vorkommt. Das heißt, k Strich ist immer kleiner oder gleich n, während der Anwendung des Z-Algorithmus. Ds haben wir ja gerade erst besprochen: das K' was im Z-Algorithmus definiert wird, ist immer kleiner gleich N. Das heißt, Z von K braucht nicht gespeichert zu werden, für Werte von k größer n.
Es wird zwar berechnet, damit man hier diese Bedingungen prüfen kann, aber es braucht nicht gespeichert zu werden, geht also nicht in den Speicherplatzbedarf ein.
Wenn man so eine Variante implementieren möchte, kann man den Z-Algorithmus praktisch abändern und einen Schwellwert einführen, bis zu dem die Z-Werte gespeichert werden.
Dann bekommen wir also einen Speicherbedarf von Oh von n.

Zum Schluss will ich noch kurz einen anderen Algorithmus erwähnen, der bekannter ist als der Z-Algorithmus.
Der Z-Algorithmus wurde, soviel ich weiß, von Dan Gusfield zuerst beschrieben, also relativ spät im Vergleich zu den frühen Algorithmen.
Ich will also kurz den Boyer-Moore-Algorithmus erwähnen, weil er außerdem noch einen anderen Vorteil hat.
Er ist benannt nach den Autoren, Boyer und Moore. Er ist schon fast 50 Jahre alt und löst genau das Problem, was wir besprochen haben, das exakte String Matching Problem.
Von dem Boyer-Moore-Algorithmus gibt es aber Varianten und eine der Varianten hat auch lineare Worst Case Laufzeit, genau wie der Z-Algorithmus.
Was jetzt allerdings meist wichtiger ist als die Worst-Case-Laufzeit, die in so extremen Fällen eintritt wie in dem, wo der Text nur aus dem gleichen Zeichen besteht,
ist mehr die erwartete Laufzeit bei typischen Texten. Für einen Erwartungswert muss man natürlich eine Verteilungsannahme treffen und die Verteilung kann natürlich von Anwendung zu Anwendung variieren.
Aber zum Beispiel könnte man als grobe Näherung ausgehen von der IID-Annahme. Das steht für Independent Identically Distributed, was man erhält, wenn man jeden Buchstaben aus einer Urne mit zurücklegen zieht. Dann hat man also unabhängige Ziehungen. In so einem Fall ist die erwartete Laufzeit sublinear. Das heißt, man braucht weniger als n plus m Vergleiche in der Erwartung. Ich will mal ganz kurz die Idee skizzieren. Von oben betrachtet ist das genauso wie beim Z-Algorithmus:
Wir prüfen, ob P in T startet an wachsenden Stellen. Also ich verschiebe P von links nach rechts in T und prüfe dann jeweils, ob es vorkommt.
Wenn es nicht vorkommt, dann wird es nach rechts geschoben. Das ist bisher auch so beim naiven Algorithmus gewesen und bei den anderen Ideen zur Beschleunigung.
Der Unterschied zu dem, was wir vorhin besprochen hatten, ist, dass man, wenn man festgestellt hat, dass P an einer Stelle nicht matcht...
Entschuldigung, man schiebt immer noch nach rechts, aber man fängt rechts an zu vergleichen. Das will ich mal gerade hier demonstrieren. Wenn ich jetzt --- sagen wir mal --- ein P hier ausgerichtet habe an einer Stelle i und ich habe jetzt hier Zeichenvergleiche gemacht --- sagen wir mal etwa so --- dann fange ich von rechts an, wie gesagt.
Dann beobachte ich ja hier irgendein Zeichen. Sagen wir mal, hier habe ich zum Beispiel das Zeichen A. Und hier habe ich ein anderes Zeichen, sagen wir B, für den Mismatch. Und dann würde ich das nächste Vorkommen von Zeichen A suchen. Wenn ich Glück habe, zum Beispiel, kommt das A ja hier gar nicht mehr drin vor. Dann kann ich das Muster komplett rausschieben.
Dann kann ich also, wenn das A hier gar nicht mehr drin vorkommt, es also so weit verschieben, und habe unter Umständen, wenn das Muster lang ist, gleich ein sehr großes Stück übersprungen. Das hängt natürlich davon ab, wo man typischerweise den Mismatch hat.
Wenn man ein großes Alphabet hat und so eine IID-Annahme treffen kann, dann kommt ja jedes bestimmte Zeichen an jeder Stelle mit kleiner Wahrscheinlichkeit vor.
Dann kann man sich also wirklich versprechen, ein langes Stück zu überspringen. Das ist diese Bad Character Rule.
Dieses A ist sozusagen ein schlechtes Zeichen, weil es nicht gematcht hat.
Dann gibt es noch eine zweite Idee, die man noch verfolgen kann. Bis dahin hat man ein Suffix, das gematcht hat und man kann auch P so vorverarbeiten, dass man eben prüft, kommt dieses Suffix hier vorher nochmal in dem Muster vor. Das am weitesten rechts liegende Vorkommen von dem Suffix definiert dann die maximale Verschiebung von dem Muster, die garantiert, dass man dabei kein Vorkommen auslässt. Mit den beiden Ideen kann man dann auch eine lineare Laufzeit erreichen, aber diesmal in "Erwartung". Je nachdem, was für Strings untersuchet, könnte das besser sein. Der Algorithmus ist in der C++-Standard-Bibliothek implementiert. Die Funktion hab hier Boyer-Moore im Namen benutzt aber bloß die Bad-Character-Rule und garantiert keine lineare Worst-Case-Laufzeit. Sie ist optimiert für eher gute erwartete Laufzeiten. Das kann man also da in Betracht ziehen, wenn man wenn man so eine exakte String Matching Funktion sucht. An dieser Stelle vielleicht nochmal kurz die allgemeine Information: Wir lernen in dieser Vorlesung lauter Algorithmen kennen. In der Praxis, wenn Sie das irgendwo später zum Beispiel in einer Firma oder auch in der Forschung einsetzen, dann werden Sie in der Regel eher eine Bibliotheksfunktion nehmen. Da wissen Sie dann, was das macht oder was man überhaupt suchen muss. Man würde aber solche Algorithmen in der Regel nicht selber noch mal implementieren, wenn Sie schon irgendwo in der Bibliothek sind, denn das es kostet zusätzlich auch noch viel Zeit, die Implementation zu testen. Man macht vielleicht erst einmal Fehler rein. Aber für Übungszwecke implementieren wir hier einige Algorithmen auch selbst.