Factorizing a String into Squares in Linear Time

DOI10.4230/LIPICS.CPM.2016.27MaRDI QIDQ5369562zbMATH OpenOpenAlexFDO

Authors Yoshiaki Matsuoka, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Florin Manea

Publication date 17 October 2017

Full work available at URL http://dx.doi.org/10.4230/LIPIcs.CPM.2016.27

zbMATH Keywords

factorization of stringsrunssquares

Mathematics Subject Classification ID

Algorithms on strings (68W32) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 3913712
• Computing all distinct squares in linear time for integer alphabets
• Efficient parallel algorithms to test square-freeness and factorize strings
• Generic Algorithms for Factoring Strings
• Squares, cubes, and time-space efficient string searching
• Computing equality-free string factorisations
• Computing equality-free and repetitive string factorisations
• Factoring into coprimes in essentially linear time
• scientific article; zbMATH DE number 799766
• String factorisations with maximum or minimum dimension

Cited in

(7)

• Factorizing strings into repetitions
• Generic Algorithms for Factoring Strings
• On the size of overlapping Lempel-Ziv and Lyndon factorizations
• scientific article; zbMATH DE number 7559452 (Why is no real title available?)
• Computing all distinct squares in linear time for integer alphabets
• Largest repetition factorization of Fibonacci words
• A fast algorithm for finding the positions of all squares in a run-length encoded string

This page was built for publication: Factorizing a String into Squares in Linear Time

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