Fast parallel Lyndon factorization with applications
From MaRDI portal
Publication:4327381
DOI10.1007/BF01191471zbMath0815.68066MaRDI QIDQ4327381
Alberto Apostolico, Maxime Crochemore
Publication date: 5 April 1995
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Related Items (19)
Parallel RAM algorithms for factorizing words ⋮ Extended suffix array construction using Lyndon factors ⋮ Indeterminate string factorizations and degenerate text transformations ⋮ Inferring strings from Lyndon factorization ⋮ Convexity preserving deformations of digital sets: characterization of removable and insertable pixels ⋮ Suffix array and Lyndon factorization of a text ⋮ On generalized Lyndon words ⋮ Finding the cyclic covers of a string ⋮ Dynamic and internal longest common substring ⋮ Optimal algorithms for computing the canonical form of a circular string ⋮ Faster Lyndon factorization algorithms for SLP and LZ78 compressed text ⋮ 2D Lyndon words and applications ⋮ On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties ⋮ Lyndon factorization algorithms for small alphabets and run-length encoded strings ⋮ Unnamed Item ⋮ Inverse Lyndon words and inverse Lyndon factorizations of words ⋮ Lyndon-like and V-order factorizations of strings ⋮ Longest Lyndon Substring After Edit ⋮ Lyndon factorization of grammar compressed texts revisited
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A public key cryptosystem based on Lyndon words
- A linear time solution to the single function coarsest partition problem
- Parallel construction of a suffix tree with applications
- Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
- Optimal canonization of all substrings of a string
- An improved algorithm to check for polygon similarity
- Factorizing words over an ordered alphabet
- Efficient Parallel Algorithms for String Editing and Related Problems
- Optimal parallel algorithms for string matching
- Relations between Concurrent-Write Models of Parallel Computation
- Fast canonization of circular strings
- Two-way string-matching
- Optimal bounds for decision problems on the CRCW PRAM
- Free differential calculus. IV: The quotient groups of the lower central series
This page was built for publication: Fast parallel Lyndon factorization with applications