## 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 = {t_{1},⋯, t_{N}} of length n and ℙ = {p_{1},⋯, pN} of length m, outputs all positions i such that {p1,⋯,pN} = {t_{1}[i: i + m - 1],⋯, t_{N} [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(m^{2} N + occ) time, where occ is the number of occurrences of the pattern ℙ in the text T. The other is memory-efficient, it requires only O(n) space, whereas the matching consumes O(m^{2} N^{2} + occ) time. We show that both of them can be constructed in O(nN) time.

Original language | English |
---|---|

Pages (from-to) | 41-53 |

Number of pages | 13 |

Journal | CEUR Workshop Proceedings |

Volume | 1326 |

Publication status | Published - 2015 |

Event | 41st International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2015 - Pec pod Snezkou, Czech Republic Duration: 2015 Jan 24 → 2015 Jan 29 |

## Keywords

- Indexing structure
- Multi-track
- String matching