Quasi-Linear-Time Algorithm for Longest Common Circular Factor

DOI10.4230/LIPICS.CPM.2019.25MaRDI QIDQ5088916zbMATH OpenOpenAlexFDO

Authors Mai Alzamel, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Juliusz Straszyński, Wiktor Zuba, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1901.11305

zbMATH Keywords

circular pattern matchinginternal pattern matchingintersection of hyperrectangleslongest common factor

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Algorithms for longest common abelian factors
• Computing longest previous factor in linear time and applications
• Longest unbordered factor in quasilinear time
• Linear time algorithm for the longest common repeat problem
• String Processing and Information Retrieval
• An almost-linear time and linear space algorithm for the longest common subsequence problem
• Linear time algorithms for generalizations of the longest common substring problem

Cites work

• A new approach to rectangle intersections part I
• Algorithms on Strings
• Alignment with non-overlapping inversions and translocations on two strings
• Average-case optimal approximate circular string matching
• Average-optimal single and multiple approximate string matching
• Average-optimal string matching
• Bit-Parallel Approximate Matching of Circular Strings with k Mismatches
• Dynamic text and static pattern matching
• Extracting powers and periods in a word from its runs structure
• Fast circular dictionary-matching algorithm
• Indexing Circular Patterns
• Internal pattern matching queries in a text and applications
• Locally Consistent Parsing for Text Indexing in Small Space
• On the sorting-complexity of suffix tree construction
• Searching and indexing circular patterns
• String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
• Suffix Arrays: A New Method for On-Line String Searches
• The ``runs theorem
• Uniqueness Theorems for Periodic Functions

Cited in

(3)

• Combinatorial Pattern Matching
• Near-optimal quantum algorithms for string problems
• Quantum speed-ups for string synchronizing sets, longest common substring, and k-mismatch matching

This page was built for publication: Quasi-Linear-Time Algorithm for Longest Common Circular Factor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5088916)