KMP Based Pattern Matching Algorithms for Multi-Track Strings
The 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), Student Research Forum,
CEUR Workshop Proceedings Vol.1548, pp.100-107
(2016), [peer-reviewed]
Event Date:
January 23-28, 2016
Abstract / 概要
Multi-track string is an $N$-tuple strings of length $n$. For two multi-track strings $\mathcal{T} = (t_1, t_2, \ldots, t_N )$ of length $n$ and $\mathcal{P} = (p_1, p_2, \ldots, p_M )$ of length $m$, permuted pattern matching is a problem to nd all positionsi such that $P$ is permuted match with $\mathcal{T}[i : i + M ]$. We propose three new algorithms for permuted pattern matching based on the KMP algorithm. The first algorithm is an exact matching algorithm that runs in $O(nN )$ time after $O(mM )$-time preprocessing. The second and third algorithms are filtering algorithms that run in $O(n(N + \sigma))$ after $O(m(M + \sigma))$-time preprocessing, where $\sigma$ is the size of alphabet. Experiments show that our algorithms run faster than AC automaton based algorithm that proposed by Katsura et al.