Efficient parallel algorithms to test square-freeness and factorize strings
From MaRDI portal
Publication:1178198
DOI10.1016/0020-0190(91)90223-5zbMath0736.68033MaRDI QIDQ1178198
Maxime Crochemore, Wojciech Rytter
Publication date: 26 June 1992
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(91)90223-5
68R05: Combinatorics in computer science
68W15: Distributed algorithms
68U15: Computing methodologies for text processing; mathematical typography
Related Items
Efficient string matching on packed texts, Parallelism and dictionary based data compression, An efficient algorithm for online square detection, P-complete problems in data compression, Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms.
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parallel construction of a suffix tree with applications
- An optimal algorithm for computing the repetitions in a word
- Optimal off-line detection of repetitions in a string
- Transducers and repetitions
- An O(n log n) algorithm for finding all repetitions in a string
- An O(logn) parallel connectivity algorithm
- A universal algorithm for sequential data compression