String-Matching-Algorithmus

In der Informatik sind String-Matching-Algorithmen eine Gruppe von Algorithmen, die das Finden von Textsegmenten in einer Zeichenkette (englisch string) anhand eines vorgegebenen Suchmusters beschreiben. Sie zählen somit zur Klasse der Zeichenkettenalgorithmen.

Im engeren Sinne suchen diese Algorithmen nach exakten Übereinstimmungen (englisch matches). Im weiteren Sinne sind auch Algorithmen gemeint, die ungefähre Übereinstimmungen zulassen, wobei der Begriff ungefähr durch ein Toleranzkriterium genau definiert sein muss.

Das Problem besteht darin, diese Aufgabe möglichst effizient zu lösen. In der Praxis ist dies bedeutsam, wenn in großen Textmengen (wie z. B. einer Wikipedia) Suchbegriffe gefunden werden sollen.