Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays

DOI10.1007/978-3-642-11266-9_25zbMath1274.68670OpenAlexW1773733719MaRDI QIDQ3401100

Costas S. Iliopoulos, Maxime Crochemore, Wojciech Rytter, Tomasz Walen, Marcin Kubica

Publication date: 28 January 2010

Published in: SOFSEM 2010: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11266-9_25

zbMATH Keywords

palindrometext compressionsuffix arrayrunslongest previous factorlongest previous non-overlapping factorlongest previous reverse factor

Mathematics Subject Classification ID

Searching and sorting (68P10) Nonnumerical algorithms (68W05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Algorithms on strings (68W32)

Related Items (10)

Extracting powers and periods in a word from its runs structure ⋮ Longest Gapped Repeats and Palindromes ⋮ Longest $$\alpha $$-Gapped Repeat and Palindrome ⋮ On Prefix/Suffix-Square Free Words ⋮ Computing longest previous non-overlapping factors ⋮ Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets ⋮ Parameterized longest previous factor ⋮ New simple efficient algorithms computing powers and runs in strings ⋮ Efficient computation of longest single-arm-gapped palindromes in a string ⋮ Searching for gapped palindromes

This page was built for publication: Efficient Algorithms for Two Extensions of LPF Table: The Power of Suffix Arrays