Bei der scheinbar einfachen Angelegenheit, eine Zeichenkette nach einem bestimmten Muster zu durchsuchen, treten unerwartet Schwierigkeiten auf, insbesondere, wenn man die Suche schnell durchführen will. Eine derartige Operation wird routinemäßig von Texteditoren und Textverarbeitungsprogrammen durchgeführt. Infolgedessen besitzt die Frage:
Wie schnell kann man eine Kette von n Zeichen nach einem bestimmten Muster durchsuchen?
eine gewisse praktische Bedeutung.