Position heaps for permuted pattern matching on multi-track strings

Takashi Katsura, Yuhei Otomo, Kazuyuki Narisawa, Ayumi Shinohara

Research output: Contribution to journalConference articlepeer-review

3 Citations (Scopus)


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 ℙ = {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(m2 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(m2 N2 + occ) time. We show that both of them can be constructed in O(nN) time.

Original languageEnglish
Pages (from-to)41-53
Number of pages13
JournalCEUR Workshop Proceedings
Publication statusPublished - 2015
Event41st International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2015 - Pec pod Snezkou, Czech Republic
Duration: 2015 Jan 242015 Jan 29


  • Indexing structure
  • Multi-track
  • String matching


Dive into the research topics of 'Position heaps for permuted pattern matching on multi-track strings'. Together they form a unique fingerprint.

Cite this