Order-preserving pattern matching with k mismatches

Paweł Gawrychowski*, Przemyslaw Uznanski

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

7 Citations (Scopus)

Abstract

We consider a generalization of the recently introduced order-preserving pattern matching. The difference between the standard pattern matching and the order-preserving variant is that instead of looking for an exact copy of the pattern, we only require that the relative order between the elements is the same. In our generalization, we additionally allow up to k mismatches between the pattern of length m and the text of length n, and the goal is to construct an efficient algorithm for small values of k. Our solution detects an order-preserving occurrence with up to k mismatches in O(n(log log m+klog log k)) time.

Original languageEnglish
Pages (from-to)136-144
Number of pages9
JournalTheoretical Computer Science
Volume638
DOIs
Publication statusPublished - 25 Jul 2016
MoE publication typeA1 Journal article-refereed

Keywords

  • Approximate pattern matching
  • Order-preserving pattern matching

Fingerprint Dive into the research topics of 'Order-preserving pattern matching with k mismatches'. Together they form a unique fingerprint.

Cite this