Optimal canonization of all substrings of a string

DOI10.1016/0890-5401(91)90016-UzbMath0757.68060MaRDI QIDQ1183603

Alberto Apostolico, Maxime Crochemore

Publication date: 28 June 1992

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

rotationLyndon wordLyndon decomposition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (10)

Linear computation of unbordered conjugate on unordered alphabet ⋮ Fast parallel Lyndon factorization with applications ⋮ Near-optimal quantum algorithms for string problems ⋮ Towards optimal packed string matching ⋮ A faster quick search algorithm ⋮ Efficient CRCW-PRAM algorithms for universal substring searching ⋮ Indexing Circular Patterns ⋮ A New String Matching Algorithm ⋮ Lyndon-like and V-order factorizations of strings ⋮ Constrained tree inclusion

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time solution to the single function coarsest partition problem
• Lexicographically least circular substrings
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• An improved algorithm to check for polygon similarity
• Factorizing words over an ordered alphabet
• Fast canonization of circular strings
• Fast Pattern Matching in Strings
• Free differential calculus. IV: The quotient groups of the lower central series

This page was built for publication: Optimal canonization of all substrings of a string