Palindrome pattern matching

DOI10.1016/j.tcs.2012.01.047zbMath1292.68183MaRDI QIDQ390901

Masayuki Takeda, Shunsuke Inenaga, Tomohiro I.

Publication date: 9 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.01.047

zbMATH Keywords

pattern matching; linear time algorithms; palindromes; suffix trees; border arrays

Mathematics Subject Classification ID

68R15: Combinatorics on words

68T10: Pattern recognition, speech recognition

68W32: Algorithms on strings

Related Items

Generalized pattern matching and periodicity under substring consistent equivalence relations

Cites Work

• Counting distinct palindromes in a word in linear time
• New trie data structures which support very fast search operations
• Palindromic richness
• Searching for gapped palindromes
• Total palindrome complexity of finite words
• Surpassing the information theoretic bound with fusion trees
• Palindrome complexity.
• On-line construction of suffix trees
• Parameterized pattern matching: Algorithms and applications
• Burrows-Wheeler transform and palindromic richness
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• Finding All Approximate Gapped Palindromes
• A New Linear-Time ``On-Line Algorithm for Finding the Smallest Initial Palindrome of a String
• Algorithms on Strings, Trees and Sequences
• Episturmian words and some constructions of de Luca and Rauzy