Compressed Consecutive Pattern Matching

Paweł Gawrychowski, Garance Gourdel, Tatiana Starikovskaya, Teresa Anna Steiner

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Originating from the work of Navarro and Thankachan [TCS 2016], the problem of consecutive pattern matching is a variant of the fundamental pattern matching problem, where one is given a text and a pair of patterns, and must compute their consecutive occurrences in the text. Assuming that the text is given as a straight-line program, we develop an algorithm that computes all consecutive occurrences in optimal time.
Original languageEnglish
Title of host publicationProceedings of the 2024 Data Compression Conference (DCC)
PublisherIEEE
Publication date2024
Pages163-172
ISBN (Print)979-8-3503-8588-5
ISBN (Electronic)979-8-3503-8587-8
DOIs
Publication statusPublished - 2024
Event2024 Data Compression Conference - Snowbird, United States
Duration: 19 Mar 202422 Mar 2024

Conference

Conference2024 Data Compression Conference
Country/TerritoryUnited States
CitySnowbird
Period19/03/202422/03/2024

Fingerprint

Dive into the research topics of 'Compressed Consecutive Pattern Matching'. Together they form a unique fingerprint.

Cite this