Knuth-Morris-Pratt

Idee: benutze den minimalen deterministischen Automaten für $\Sigma^{*}_{}$m$\Sigma^{*}_{}$.

• nichtdeterministischer Automat mit | m| + 1 Zuständen
• Potenzmengenkonstruktion
• vereinfache die Zustandsbezeichnungen
• beschreibe Zustandsübergänge durch failure function
• Laufzeit?
• Beste/schlechteste Fälle?