2026-07-26T04:50:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12087 2024-03-06T10:49:19Z ddc:004 open_access

Fast and Linear-Time String Matching Algorithms Based on the Distances of q-Gram Occurrences Kobayashi, Satoshi Hendrian, Diptarama Yoshinaka, Ryo Shinohara, Ayumi String matching algorithm text processing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Satoshi Kobayashi and Diptarama Hendrian and Ryo Yoshinaka and Ayumi Shinohara 2020 Is Part Of LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2020.13 urn:nbn:de:0030-drops-120878 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.13 eng https://creativecommons.org/licenses/by/3.0/legalcode