Efficient counting of square substrings in a tree

DOI10.1016/J.TCS.2014.04.015MaRDI QIDQ2250458zbMATH OpenOpenAlexFDO

Authors Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Jakub W. Pachocki, Tomasz Waleń

Publication date 7 July 2014

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

Full work available at URL https://doi.org/10.1016/j.tcs.2014.04.015

zbMATH Keywords

pattern matchingsquare in stringtree

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Recommendations

• Efficient counting of square substrings in a tree
• Fast Counting with Bounded Treewidth
• Squares, cubes, and time-space efficient string searching
• A sublinear time string prefix square detection algorithm
• The Efficient Computation of Complete and Concise Substring Scales with Suffix Trees
• Subset counting in trees
• An optimal algorithm for computing all subtree repeats in trees
• An optimal algorithm for computing all subtree repeats in trees
• Near-optimal algorithm to count occurrences of subsequences of a given length
• Linear-time period computation of a string with suffix trees

Cites work

• A note on the number of squares in a word
• A simple proof that a word of length \(n\) has at most \(2n\) distinct squares
• An O(n log n) algorithm for finding all repetitions in a string
• Counting distinct squares in partial words
• Efficient counting of square substrings in a tree
• Fast Algorithms for Finding Nearest Common Ancestors
• How many squares can a string contain?
• scientific article; zbMATH DE number 1522932 (Why is no real title available?)
• Jewels of Stringology
• Linear time algorithms for finding and representing all the tandem repeats in a string
• New simple efficient algorithms computing powers and runs in strings
• Nonrepetitive colorings of graphs
• Nonrepetitive colorings of trees
• Nonrepetitive list colourings of paths
• Repetitions in strings: algorithms and combinatorics
• Results and trends in theoretical computer science, Colloquium in honor of Arto Salomaa, Graz, Austria, June 10-11, 1994. Proceedings
• The level ancestor problem simplified
• The maximum number of squares in a tree

Cited in

(13)

• String powers in trees
• Squares, cubes, and time-space efficient string searching
• String covers of a tree
• The maximum number of squares in a tree
• String Powers in Trees
• Efficient counting of square substrings in a tree
• Computing runs on a trie
• Computing all distinct squares in linear time for integer alphabets
• Fast Counting with Bounded Treewidth
• Tight bound for the number of distinct palindromes in a tree
• A new linear-time algorithm for centroid decomposition
• String covers of a tree revisited
• Efficiently computing runs on a trie

This page was built for publication: Efficient counting of square substrings in a tree

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