Name
Abstract | ||
|---|---|---|
We present several efficient data structures for answering queries related to periods in words. For a given word w of length n the Period Query given a factor of w (represented by an interval) returns its shortest period and a compact representation of all periods. Several algorithmic solutions are proposed that balance the data structure space (ranging from O(n) to O(nlogn)), and the query time complexity (ranging from O(log1+εn) to O(logn)). |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-34109-0_30 | SPIRE |
Keywords | Field | DocType |
query time complexity,efficient data structure,shortest period,algorithmic solution,period query,length n,compact representation,factor periodicity problem,word w,data structure space | Discrete mathematics,Data structure,Ranging,Time complexity,Mathematics,Arithmetic progression | Conference |
Volume | ISSN | Citations |
7608 | 0302-9743 | 11 |
PageRank | References | Authors |
0.65 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tomasz Kociumaka | 1 | 217 | 38.57 |
| Jakub Radoszewski | 2 | 624 | 50.36 |
| Wojciech Rytter | 3 | 2290 | 181.52 |
| Tomasz Waleń | 4 | 706 | 39.62 |