License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2020.13
URN: urn:nbn:de:0030-drops-120878
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12087/
Go to the corresponding LIPIcs Volume Portal

Kobayashi, Satoshi ; Hendrian, Diptarama ; Yoshinaka, Ryo ; Shinohara, Ayumi

Fast and Linear-Time String Matching Algorithms Based on the Distances of q-Gram Occurrences

pdf-format:
LIPIcs-SEA-2020-13.pdf (0.6 MB)

Abstract

Given a text T of length n and a pattern P of length m, the string matching problem is a task to find all occurrences of P in T. In this study, we propose an algorithm that solves this problem in O((n + m)q) time considering the distance between two adjacent occurrences of the same q-gram contained in P. We also propose a theoretical improvement of it which runs in O(n + m) time, though it is not necessarily faster in practice. We compare the execution times of our and existing algorithms on various kinds of real and artificial datasets such as an English text, a genome sequence and a Fibonacci string. The experimental results show that our algorithm is as fast as the state-of-the-art algorithms in many cases, particularly when a pattern frequently appears in a text.

BibTeX - Entry

@InProceedings{kobayashi_et_al:LIPIcs:2020:12087,
  author =	{Satoshi Kobayashi and Diptarama Hendrian and Ryo Yoshinaka and Ayumi Shinohara},
  title =	{{Fast and Linear-Time String Matching Algorithms Based on the Distances of q-Gram Occurrences}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{13:1--13:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Simone Faro and Domenico Cantone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12087},
  URN =		{urn:nbn:de:0030-drops-120878},
  doi =		{10.4230/LIPIcs.SEA.2020.13},
  annote =	{Keywords: String matching algorithm, text processing}
}

Keywords: String matching algorithm, text processing
Collection: 18th International Symposium on Experimental Algorithms (SEA 2020)
Issue Date: 2020
Date of publication: 12.06.2020
Supplementary Material: The implementations of our algorithms are available at https://github.com/ushitora/distq.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI