Space efficient search for maximal repetitions
From MaRDI portal
Publication:557913
DOI10.1016/J.TCS.2005.01.006zbMATH Open1076.68054OpenAlexW1984098563MaRDI QIDQ557913FDOQ557913
Authors: Leszek Gąsieniec, Igor Potapov, Roman Kolpakov 
Publication date: 30 June 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.01.006
Recommendations
- scientific article; zbMATH DE number 2051171
- scientific article; zbMATH DE number 2087050
- Faster algorithms for computing maximal multirepeats in multiple sequences
- Efficient repeat finding in sets of strings via suffix arrays
- Almost linear time computation of maximal repetitions in run length encoded strings
- Optimal Parallel Searching an Array for Certain Repetitions
- scientific article; zbMATH DE number 2052916
- Fast algorithms for finding a minimum repetition representation of strings and trees
- Space-time trade-offs for finding shortest unique substrings and maximal unique matches
Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Number-theoretic algorithms; complexity (11Y16) Descriptive complexity and finite models (68Q19)
Cites Work
- Algorithms on Strings, Trees and Sequences
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Time-space-optimal string matching
- Squares, cubes, and time-space efficient string searching
- An O(n log n) algorithm for finding all repetitions in a string
- The zooming method: A recursive approach to time-space efficient string-matching
Cited In (13)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Some results on the number of periodic factors in words
- Time-Space Trade-Offs for Longest Common Extensions
- Two-dimensional maximal repetitions
- Faster algorithms for computing maximal multirepeats in multiple sequences
- On primary and secondary repetitions in words
- Online detection of repetitions with backtracking
- Almost linear time computation of maximal repetitions in run length encoded strings
- Time-space trade-offs for longest common extensions
- Searching runs in streams
- On maximal repeats in strings
- An O(n log n) algorithm for finding all repetitions in a string
This page was built for publication: Space efficient search for maximal repetitions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q557913)
