✦ LIBER ✦

Pattern Matching with Swaps

✍ Scribed by Amihood Amir; Yonatan Aumann; Gad M. Landau; Moshe Lewenstein; Noa Lewenstein

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 146 KB
Volume: 37
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2000.1120

No coin nor oath required. For personal study only.

✦ Synopsis

Let a text string T of n symbols and a pattern string P of m symbols from alphabet be given. A swapped version T of T is a length n string derived from T by a series of local swaps (i.e., t ← t +1 and t +1 ← t ), where each element can participate in no more than one swap. The pattern matching with swaps problem is that of finding all locations i for which there exists a swapped version T of T with an exact matching of P in location i of T . It has been an open problem whether swapped matching can be done in less than O nm time. In this paper we show the first algorithm that solves the pattern matching with swaps problem in time o nm . We present an algorithm whose time complexity is O nm 1/3 log m log σ for a general alphabet , where σ = min m .

📜 SIMILAR VOLUMES

Efficient Algorithms for Approximate Str

Efficient Algorithms for Approximate String Matching with Swaps

✍ Dong Kyue Kim; Jee-Soo Lee; Kunsoo Park; Yookun Cho 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 357 KB

Inverse Pattern Matching

✍ Amihood Amir; Alberto Apostolico; Moshe Lewenstein 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 181 KB

Let a textstring T of n symbols from some alphabet ⌺ and an integer mn be given. A pattern P of length m over ⌺ is sought such that P minimizes Ž . alternatively, maximizes the total number of pairwise character mismatches generated when P is compared with all m-character substrings of T. Two additi

Two-dimensional pattern matching with k

Two-dimensional pattern matching with k mismatches

✍ Sanjay Ranka; Todd Heywood 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 700 KB

Pattern Matching in Hypertext

✍ Amihood Amir; Moshe Lewenstein; Noa Lewenstein 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 142 KB

The importance of hypertext has been steadily growing over the past decade. The Internet and other information systems use hypertext format, with data organized associatively rather than sequentially or relationally. A myriad of textual problems have been considered in the pattern matching field wit

Fastest Pattern Matching in Strings

✍ L. Colussi 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 850 KB

An algorithm is presented that substantially improves the algorithm of Boyer and Moore for pattern matching in strings, both in the worst case and in the average. Both the Boyer and Moore algorithm and the new algorithm assume that the characters in the pattern and in the text are taken from a given

Pattern matching in historical data

✍ Michael C. Johannesmeyer; Ashish Singhal; Dale E. Seborg 📂 Article 📅 2002 🏛 American Institute of Chemical Engineers 🌐 English ⚖ 581 KB