Name
Abstract | ||
|---|---|---|
The computation of the least lexicographic rotation of a string leads to the identification of polygon similarity. An O(logn) time CRCW PRAM algorithm for computing the least lexicographic rotation of a circular string (of length n) over a fixed alphabet is presented here. The logarithmic running time is achieved by using O(n/logn) processors and its space complexity is linear. A second algorithm for unbounded alphabets requires O(lognloglogn) units of time, uses O(n/logn) processors. |
Year | DOI | Venue |
|---|---|---|
1989 | 10.1007/3-540-51859-2_4 | Optimal Algorithms |
Keywords | Field | DocType |
polygon similarity,identifying polygon similarity,pram algorithm,pram algorithms,space complexity | Discrete mathematics,Polygon,Combinatorics,Algorithm,Binary tree,Logarithm,Unit of time,Suffix tree,Lexicographical order,Mathematics,Computation,Alphabet | Conference |
Volume | ISSN | ISBN |
401 | 0302-9743 | 0-387-51859-2 |
Citations | PageRank | References |
1 | 0.38 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| C. S. Iliopoulos | 1 | 52 | 6.67 |
| W. F. Smyth | 2 | 730 | 68.91 |