SERIOUS-PLAYGROUND.DE/blog/

Das String-Matching-Problem besteht darin, in einem gegebenen Text ein Muster zu suchen. Meistens sind Text und Muster Strings, d.h. Zeichenketten, und man will das Muster als Teilstring im Text finden. Dieses Problem tritt zum Beispiel in einem Texteditor auf, in dem man ein bestimmtes Wort sucht (oder alle Vorkommen eines bestimmten Wortes oder Zeichens mit einem anderen Zeichen oder Wort ersetzen möchte), in Suchmaschinen, die das Internet durchforsten oder im Bereich der Molekularbiologie: hier sucht man beispielsweise in einer Sequenzdatenbank nach einer bestimmten Sequenz oder einem Teilstück einer Sequenz.

Das String-Matching-Problem wird folgendermaßen formal definiert:
Sei Σ ein beliebiges Alphabet. Das (exakte) String-Matching-Problem ist das folgende Berechnungsproblem:

Gegeben sind zwei Strings t (der Text, in dem gesucht wird) und p (das Muster, welches gesucht wird), mit t=t₁…t_n und p=p₁…p_m über dem Alphabet Σ. (Beachte, dass der Index hier bei 1 beginnt! In einer Implementierung wird in Arrays und Strings bei Position 0 begonnen!). n ist hier die Länge des Textes und m die Länge des Musters (d.h. die Anzahl der einzelnen Zeichen in den jeweligen Strings).

Die Ausgabe ist die Menge aller Positionen im Text t, an denen das Muster p beginnt. Gesucht ist also eine Menge I ⊆ {1, …, n-m+1} von Indizes, so dass i ∈ I genau dann, wenn t_i…t_i+m-1 = p.

Beispiel:

Suche im Text t=”qwertzuiopüstring-matchingstringf” das Pattern p=”string”. Das Ergebnis ist die Menge I={12, 27}, da das Muster p an diesen Positionen im Text t beginnt:

“qwertzuiopüstring-matchingstringf”

Eine Übersicht über String-Matching-Algorithmen findet man hier. Ich werde demnächst auch ein paar interessante Algorithmen hier vorstellen. Muss ans Telephon…