Der Z-Algorithm ist ein effizienter Algorithmus zur Mustererkennung in Strings, der die Z-Array-Datenstruktur verwendet. Das Z-Array für eine gegebene Zeichenkette ist ein Array, bei dem jeder Index den Wert enthält, der die Länge des längsten Präfixes von , das auch als Suffix beginnt, ab dem Index . Der Algorithmus berechnet das Z-Array in linearer Zeit, also in , wobei die Länge der Zeichenkette ist.
Das Z-Array ermöglicht es, schnell zu überprüfen, ob ein Muster in einem Text vorkommt, indem man die Werte im Z-Array mit der Länge des Musters vergleicht. Die Hauptanwendung des Z-Algorithmus besteht darin, die Suche nach Mustern in Texten oder großen Datenmengen zu optimieren, was ihn besonders nützlich in der Bioinformatik, Textverarbeitung und Datenkompression macht.
Starte dein personalisiertes Lernelebnis mit acemate. Melde dich kostenlos an und finde Zusammenfassungen und Altklausuren für deine Universität.