Position Heaps for Permuted Pattern Matching on Multi-Track String.
SOFSEM2015,
Proceedings of Student Research Forum Papers and Posters at SOFSEM 2015, pp.41-53
(2015), [peer-reviewed]
Event Date:
January 24-29, 2015
@ Pec pod Sněžkou, Czech Republic
- Pec pod Sněžkou, Czech Republic
- Czech Republic
- SOFSEM
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, \ldots, t_N }$ of length $n$ and $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+occ)$ time, where $occ$ is the number of occurrences of the pattern $P$ in the text $T$. The other is memory-e cient, 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.