Efficient counting of square substrings in a tree

DOI10.1016/j.tcs.2014.04.015zbMath1418.68250OpenAlexW1970774636MaRDI QIDQ2250458

Wojciech Rytter, Tomasz Kociumaka, Jakub Radoszewski, Jakub W. Pachocki, Tomasz Walen

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

treepattern matchingsquare in string

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items (6)

Efficiently computing runs on a trie ⋮ String covers of a tree ⋮ String Powers in Trees ⋮ String powers in trees ⋮ Tight bound for the number of distinct palindromes in a tree ⋮ Computing runs on a trie

Cites Work

• Unnamed Item
• Unnamed Item
• New simple efficient algorithms computing powers and runs in strings
• The level ancestor problem simplified
• Nonrepetitive colorings of trees
• Repetitions in strings: algorithms and combinatorics
• How many squares can a string contain?
• Results and trends in theoretical computer science, Colloquium in honor of Arto Salomaa, Graz, Austria, June 10-11, 1994. Proceedings
• Linear time algorithms for finding and representing all the tandem repeats in a string
• 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
• The Maximum Number of Squares in a Tree
• Nonrepetitive list colourings of paths
• Fast Algorithms for Finding Nearest Common Ancestors
• An O(n log n) algorithm for finding all repetitions in a string
• Jewels of Stringology
• Efficient Counting of Square Substrings in a Tree
• Nonrepetitive colorings of graphs

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