A New Linear-Time On-Line Algorithm for Palindrome Identification
Discover the innovative linear-time on-line algorithm by Glenn Manacher for finding the smallest initial palindrome of a string. This groundbreaking approach solves the long-standing challenge of recognizing the leftmost nonvoid palindrome by examining only the relevant symbols. Learn how this algorithm operates independently of the input alphabet size, allowing for easy extension to recognize both odd and even palindromes. Explore the potential real-time recognition of specific string patterns on a defined random access machine.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
A New Linear-Time "On-Line" Algorithm for Finding the Smallest Initial Palindrome of a String Glenn Manacher Journal of the ACM 22(1975) 346-351 Presenter: Cheng-Han Ho Date: Mar. 7, 2023
Abstract (1/2) Despite significant advances in linear-time scanning algorithms, particularly those based wholly or in part on either Cook's linear- time simulation of two-way deterministic pushdown automata or Weiner's algorithm, the problem of recognizing the initial leftmost nonvoid palindrome of a string in time proportional to the length N of the palindrome, examining no symbols other than those in the palindrome, has remained open. The present algorithm solves this problem, assuming that addition of two integers less than or equal to N may be performed in a single operation.
Abstract (2/2) Like the Knuth-Morris-Pratt algorithm, it runs in time independent of the size of the input alphabet. The algorithm as presented finds only even palindromes. However, an extension allows one to recognize the initial odd or even palindrome of length 2 or greater. Other easy extensions permit the recognition of strings (wwR)* of even palindromes and of all the initial palindromes. It appears possible that further extension may be used to show that (wwR) * is in a sense recognizable in real time on a reasonably defined random access machine.
Palindrome ? = aabaa ? = aabbaa ? = aabaa ? = aabbaa ? = ? w is a palindrome ? = ? w is a palindrome
O(n2) algorithm ? = abbabaababa ? = a-b-b-a-b-a-a-b-a-b-a O(n2)
ManachersAlgorithm (1/7) c~x a r 3 r = < x : cbabxbabc 1. r = x > x : cbabcxcbabe 2. r = x : cbabxbabxbac 3.
ManachersAlgorithm (2/7) ? = cbabxbabxbac i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 w c - b - a - b - x - b - a - b - x - b - a - c r 1 1 2 1 4
ManachersAlgorithm (3/7) ? = cbabxbabxbac i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 w c - b - a - b - x - b - a - b - x - b - a - c r 1 1 2 1 4 1 2 1
ManachersAlgorithm (4/7) ? = cbabxbabxbac i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 w c - b - a - b - x - b - a - b - x - b - a - c r 1 1 2 1 4 1 2 1 8
ManachersAlgorithm (5/7) ? = cbabxbabxbac i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 w c - b - a - b - x - b - a - b - x - b - a - c r 1 1 2 1 4 1 2 1 8 1 2 1 10
ManachersAlgorithm (6/7) ? = cbabxbabxbac i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 w c - b - a - b - x - b - a - b - x - b - a - c r 1 1 2 1 4 1 2 1 8 1 2 1 10 1 2 1 6
ManachersAlgorithm (7/7) ? = cbabxbabxbac i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 w c - b - a - b - x - b - a - b - x - b - a - c r 1 1 2 1 4 1 2 1 8 1 2 1 10 1 2 1 6 1 2 1 1 1 1
Complexity n: m: time complexity = O(n / m) * m = O(n)
