Abstract | ||
---|---|---|
Recently Kubica et al. (Inf. Process. Let., 2013) and Kim et al. (submitted to Theor. Comp. Sci.) introduced order-preserving pattern matching. In this problem we are looking for consecutive substrings of the text that have the same "shape" as a given pattern. These results include a linear-time order-preserving pattern matching algorithm for polynomially-bounded alphabet and an extension of this result to pattern matching with multiple patterns. We make one step forward in the analysis and give an $O(\frac{n\log{n}}{\log\log{n}})$ time randomized algorithm constructing suffix trees in the order-preserving setting. We show a number of applications of order-preserving suffix trees to identify patterns and repetitions in time series. |
Year | Venue | Field |
---|---|---|
2013 | CoRR | String searching algorithm,Discrete mathematics,Randomized algorithm,Combinatorics,Substring,Suffix,Pattern matching,Mathematics,Alphabet |
DocType | Volume | Citations |
Journal | abs/1303.6872 | 2 |
PageRank | References | Authors |
0.42 | 3 | 9 |
Name | Order | Citations | PageRank |
---|---|---|---|
Maxime Crochemore | 1 | 2655 | 281.75 |
Costas S. Iliopoulos | 2 | 1534 | 167.43 |
Tomasz Kociumaka | 3 | 217 | 38.57 |
Marcin Kubica | 4 | 629 | 29.26 |
Alessio Langiu | 5 | 46 | 6.52 |
Solon P. Pissis | 6 | 281 | 57.09 |
Jakub Radoszewski | 7 | 624 | 50.36 |
Wojciech Rytter | 8 | 2290 | 181.52 |
Tomasz Waleń | 9 | 706 | 39.62 |