Name
Abstract | ||
|---|---|---|
A multi-set of N strings of length n is called a multi-track string. The permuted pattern matching is the problem that given two multi-track strings T = {t1, . . . , tN} of length n and P = {p1, . . . , pN} of length m, outputs all positions i such that {p1, . . . , pN} = {t1[i : i+m−1], . . . , tN [i : i+m−1]}We propose two new indexing structures for multi-track stings. One is a time-efficient structure for T that needs O(nN) space and enables us to solve the problem in O(mN+occ) time, where occ is the number of occurrences of the pattern P in the text T. The other is memory-efficient, it requires only O(n) space, whereas the matching consumes O(mN + occ) time. We show that both of them can be constructed in O(nN) time. |
Year | Venue | Field |
|---|---|---|
2015 | SOFSEM (Student Research Forum Papers / Posters) | Discrete mathematics,Search engine indexing,Heap (data structure),Pattern matching,Mathematics |
DocType | Citations | PageRank |
Conference | 1 | 0.43 |
References | Authors | |
8 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takashi Katsura | 1 | 54 | 5.91 |
| Yuhei Otomo | 2 | 2 | 0.81 |
| Kazuyuki Narisawa | 3 | 33 | 6.82 |
| Ayumi Shinohara | 4 | 936 | 88.28 |