TY - GEN

T1 - Overlap matching

AU - Amir, Amihood

AU - Cole, Richard

AU - Hariharan, Ramesh

AU - Lewenstein, Moshe

AU - Porat, Ely

N1 - Copyright:
Copyright 2012 Elsevier B.V., All rights reserved.

PY - 2001

Y1 - 2001

N2 - 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;).

AB - 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;).

KW - Algorithms

KW - Theory

KW - Verification

UR - http://www.scopus.com/inward/record.url?scp=0006330494&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0006330494&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0006330494

SN - 0898714907

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 279

EP - 288

BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 2001 Operating Section Proceedings, American Gas Association

Y2 - 30 April 2001 through 1 May 2001

ER -