Computing all distinct squares in linear time for integer alphabets

DOI10.4230/LIPICS.CPM.2017.22MaRDI QIDQ5110887zbMATH OpenFDO

Authors Hideo Bannai, Shunsuke Inenaga, Dominik Köppl

Publication date 25 May 2020

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

zbMATH Keywords

counting algorithmsdistinct squarestandem repeats

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Recommendations

• Efficient counting of square substrings in a tree
• Efficient counting of square substrings in a tree
• scientific article; zbMATH DE number 3913712
• A fast algorithm for finding the positions of all squares in a run-length encoded string
• Factorizing a String into Squares in Linear Time

Cited in

(17)

• Improved upper bounds on all maximal -gapped repeats and palindromes
• Internal dictionary matching
• Two-dimensional maximal repetitions
• Sensitivity of string compressors and repetitiveness measures
• A computational substantiation of the d-step approach to the number of distinct squares problem
• scientific article; zbMATH DE number 1305471 (Why is no real title available?)
• Efficient counting of square substrings in a tree
• Small-space LCE data structure with constant-time queries
• Factorizing a String into Squares in Linear Time
• The number of repetitions in 2D-strings
• Practical Performance of Space Efficient Data Structures for Longest Common Extensions.
• Shortest covers of all cyclic shifts of a string
• Efficient enumeration of non-equivalent squares in partial words with few holes
• On longest common property preserved substring queries
• Optimal bounds for distinct quartics
• Counting distinct square substrings in sublinear time
• Fast computation of k-runs, parameterized squares, and other generalised squares

This page was built for publication: Computing all distinct squares in linear time for integer alphabets

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