Position Heaps for Permuted Pattern Matching on Multi-Track String
The 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2015), Student Research Forum,
CEUR Workshop Proceedings, pp.41-53
(2015), [peer-reviewed]
Event Date:
January 24-29, 2015
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 $\mathcal{T} = { t_1, \ldots, t_N }$ of length $n$ and $\mathcal{P} = {p_1, \ldots, p_{N}}$ of length $m$, outputs all positions $i$ such that ${p_1 \ldots, p_N} = {t_1[i : i + m_1], \ldots, t_N[i:i+m_1]}$. We propose two newi ndexing 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+\mathit{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(m^2 N^2 + \mathit{occ})$ time. We show that both of them can be constructed in $O(nN)$ time.