Squares, cubes, and time-space efficient string searching
From MaRDI portal
Publication:1894296
DOI10.1007/BF01190846zbMath0849.68044OpenAlexW1968517468MaRDI QIDQ1894296
Wojciech Rytter, Maxime Crochemore
Publication date: 9 August 1995
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01190846
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Combinatorics on words (68R15) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)
Related Items (66)
On maximal suffixes and constant-space linear-time versions of KMP algorithm. ⋮ Clusters of repetition roots: single chains ⋮ Factorizing strings into repetitions ⋮ Square-free words with one possible mismatch ⋮ A note on the number of squares in a word ⋮ More results on overlapping squares ⋮ The new periodicity lemma revisited ⋮ ASYMPTOTIC BEHAVIOUR OF THE MAXIMAL NUMBER OF SQUARES IN STANDARD STURMIAN WORDS ⋮ Lower bounds for the number of repetitions in 2D strings ⋮ ZIV-LEMPEL AND CROCHEMORE FACTORIZATIONS OF THE GENERALIZED PERIOD-DOUBLING WORD ⋮ Data structures and algorithms for the string statistics problem ⋮ Distinct squares in run-length encoded strings ⋮ Searching of gapped repeats and subrepetitions in a word ⋮ Simple real-time constant-space string matching ⋮ Lyndon words and Fibonacci numbers ⋮ On the number of \(k\)-powers in a finite word ⋮ Constructing Words with High Distinct Square Densities ⋮ Large-scale detection of repetitions ⋮ Finding approximate repetitions under Hamming distance. ⋮ The three squares lemma revisited ⋮ The three-squares lemma for partial words with one hole ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the number of gapped repeats with arbitrary gap ⋮ From Bi-ideals to Periodicity ⋮ Bounds on Powers in Strings ⋮ How many double squares can a string contain? ⋮ Prefix-suffix duplication ⋮ Maximal repetitions in strings ⋮ WORD COMPLEXITY AND REPETITIONS IN WORDS ⋮ Partial words and the critical factorization theorem revisited ⋮ On a lemma of Crochemore and Rytter ⋮ A \(d\)-step approach to the maximum number of distinct squares and runs in strings ⋮ Distinct Squares in Circular Words ⋮ Simple Real-Time Constant-Space String Matching ⋮ Square network on a word ⋮ Efficient on-line repetition detection ⋮ The maximal number of cubic runs in a word ⋮ Computing regularities in strings: a survey ⋮ On the maximum number of cubic subwords in a word ⋮ Shortest covers of all cyclic shifts of a string ⋮ Linear-time computation of local periods ⋮ NUMBER OF OCCURRENCES OF POWERS IN STRINGS ⋮ Partial words and the critical factorization theorem ⋮ Space efficient search for maximal repetitions ⋮ Optimal bounds for computing \({\alpha}\)-gapped repeats ⋮ On the number of squares in partial words ⋮ Simple and flexible detection of contiguous repeats using a suffix tree ⋮ Periods in extensions of words ⋮ Existence of words over three-letter alphabet not containing squares with replacement errors ⋮ A NEW PROOF OF THE THREE-SQUARES LEMMA FOR PARTIAL WORDS WITH ONE HOLE ⋮ Two-dimensional maximal repetitions ⋮ On the Prefix–Suffix Duplication Reduction ⋮ How many squares can a string contain? ⋮ Intersecting periodic words ⋮ Computing runs on a trie ⋮ Periodicity and the golden ratio ⋮ On primary and secondary repetitions in words ⋮ Repetitions in strings: algorithms and combinatorics ⋮ The exact number of squares in Fibonacci words ⋮ A simple proof that a word of length \(n\) has at most \(2n\) distinct squares ⋮ Existence of words over a binary alphabet free from squares with mismatches ⋮ A multidimensional critical factorization theorem ⋮ Clusters of repetition roots forming prefix chains ⋮ Efficient enumeration of non-equivalent squares in partial words with few holes ⋮ Three overlapping squares: the general case characterized \& applications
Cites Work
This page was built for publication: Squares, cubes, and time-space efficient string searching
