Two-dimensional maximal repetitions

DOI10.1016/j.tcs.2019.07.006zbMath1435.68394OpenAlexW2953677542WikidataQ127552080 ScholiaQ127552080MaRDI QIDQ2297850

Dina Sokol, Gad M. Landau, Shoshana Marcus, Amihood Amir

Publication date: 20 February 2020

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9465/

zbMATH Keywords

periodicitypattern matching algorithmstwo-dimensional repetitions

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (6)

Upper bounds on distinct maximal (sub-)repetitions in compressed strings ⋮ Multidimensional period recovery ⋮ Lower bounds for the number of repetitions in 2D strings ⋮ Two-dimensional Fibonacci words: tandem repeats and factor complexity ⋮ Unnamed Item ⋮ Tight Upper Bounds on Distinct Maximal (Sub-)Repetitions in Highly Compressible Strings

Cites Work

• Periodicity in rectangular arrays
• Extracting powers and periods in a word from its runs structure
• 2D Lyndon words and applications
• Repetitions in strings: algorithms and combinatorics
• Fibonacci arrays and their two-dimensional repetitions
• Linear time algorithms for finding and representing all the tandem repeats in a string
• Squares, cubes, and time-space efficient string searching
• On-line construction of suffix trees
• Optimal discovery of repetitions in 2D
• Coverability in Two Dimensions
• Fast parallel and serial approximate string matching
• Two-Dimensional Periodicity in Rectangular Arrays
• A Constant Time Optimal Parallel Algorithm for Two-Dimensional Pattern Matching
• The “Runs” Theorem
• Internal Pattern Matching Queries in a Text and Applications
• A new characterization of maximal repetitions by Lyndon trees
• Unnamed Item
• Unnamed Item

This page was built for publication: Two-dimensional maximal repetitions