Manacher's Algorithm ist ein effizienter Algorithmus zur Bestimmung der längsten palindromischen Teilzeichenkette in einer gegebenen Zeichenkette. Der Algorithmus hat eine Zeitkomplexität von , was ihn erheblich schneller macht als naive Methoden, die eine Zeitkomplexität von aufweisen. Er funktioniert durch die Verwendung eines transformierten Strings, in dem zwischen jedem Zeichen und an den Rändern Platzhalter (z. B. #
) eingefügt werden, um die Behandlung von geraden und ungeraden Palindromen zu vereinheitlichen.
Der Algorithmus erstellt ein Array, das die Längen der Palindrome für jeden Index im transformierten String speichert, und nutzt dabei die bereits berechneten Werte, um die Berechnung für die nächsten Indizes zu optimieren. Diese effiziente Nutzung vorheriger Ergebnisse ermöglicht es, die maximale Palindromlänge in linearer Zeit zu finden, was den Algorithmus besonders nützlich für Anwendungen in der Textverarbeitung und mustererkennenden Algorithmen macht.
Starte dein personalisiertes Lernelebnis mit acemate. Melde dich kostenlos an und finde Zusammenfassungen und Altklausuren für deine Universität.