Overlap matching

Amihood Amir, Richard Cole, Ramesh Hariharan, Moshe Lewenstein, Ely Porat

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and patterns are singled out, say intervals. A "match" is a text location where a specified relation between the text and pattern areas is satisfied. In particular we define the structural matching problem of Overlap (Parity) Matching. We seek the text locations where all overlaps of the given pattern and text intervals have even length. We show that this problem can be solved in time &Ogr;(n log m), where the text length is n and the pattern length is m. As an application of overlap matching, we show how to reduce the String Matching with Swaps problem to the overlap matching problem. The String Matching with Swaps problem is the problem of string matching in the presence of local swaps. The best known deterministic upper bound for this problem was &Ogr;(nm 1/3 log m log &sgr;) for a general alphabet Z, where &sgr; = min(m, |σ|. Our reduction provides a solution to the pattern matching with swaps problem in time &Ogr;(n log m log &sgr;).

Original languageEnglish (US)
Title of host publicationProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Number of pages10
StatePublished - 2001
Event2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States
Duration: Apr 30 2001May 1 2001

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other2001 Operating Section Proceedings, American Gas Association
Country/TerritoryUnited States
CityDallas, TX


  • Algorithms
  • Theory
  • Verification

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Overlap matching'. Together they form a unique fingerprint.

Cite this