Optimal parallel detection of squares in strings
From MaRDI portal
Publication:1194333
DOI10.1007/BF01758848zbMath0748.68022MaRDI QIDQ1194333
Publication date: 27 September 1992
Published in: Algorithmica (Search for Journal in Brave)
string matching; combinatorial algorithms on words; avoidable regularities; squares and repetitions in a string
68Q25: Analysis of algorithms and problem complexity
68R15: Combinatorics on words
68W15: Distributed algorithms
Related Items
Efficient string matching on packed texts, Efficient detection of quasiperiodicities in strings, An efficient algorithm for online square detection, String-matching on ordered alphabets, Efficient CRCW-PRAM algorithms for universal substring searching, Optimal discovery of repetitions in 2D
Cites Work
- The equation \(a_ M=b^ Nc^ P\) in a free group
- Structural properties of the string statistics problem
- 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
- Usefulness of the Karp-Miller-Rosenberg algorithm in parallel computations on strings and arrays
- Factorizing words over an ordered alphabet
- An O(n log n) algorithm for finding all repetitions in a string
- Efficient Parallel Algorithms for String Editing and Related Problems
- Relations between Concurrent-Write Models of Parallel Computation
- Bounds for the String Editing Problem
- Free differential calculus. IV: The quotient groups of the lower central series
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item