Efficient Parameterized Pattern Matching in Sublinear Space
String Processing and Information Retrieval - 30th International Symposium, SPIRE 2023,
Lecture Notes in Computer Science Vol.14240, pp.271-283
(2023), [peer-reviewed]
Event Date:
September 26-28, 2023
Abstract / 概要
The parameterized matching problem is a variant of string matching, which is to search for all parameterized occurrences of a pattern $P$ in a text $T$. In considering matching algorithms, the combinatorial natures of strings, especially periodicity, play an important role. In this paper, we analyze the properties of periods of parameterized strings and propose a generalization of Galil and Seiferas’s exact matching algorithm (1980) into parameterized matching, which runs in $O(\pi|T|+|P|)$ time and $O(\log{|P|} + |\Pi|)$ space in addition to the input space, where $\Pi$ is the parameter alphabet and $\pi$ is the number of parameter characters appearing in P plus one.