Abstract

String matching problem received much attention over the years due to its importance in various applications such as text/file comparison, DNA sequencing, search engines, and spelling correction. Especially with the introduction of search engines dealing with tremendous amount of textual information presented on the world wide web and the research on DNA sequencing, this problem deserves special attention and any algorithmic or hardware improvements to speed up the process will benefit these important applications.

In this paper, we present three algorithms for string matching on reconfigurable mesh architectures. Given a text T of length n and a pattern P of length m, the first algorithm finds the exact matching between T and Pin 0(1) time on a 2-dimensional RMESH of size (n-m+l) xm. The second algorithm finds the approximate matching between T and P in O(k) time on a 2D RMESH, where k is the maximum edit distance between T and P. The third algorithm allows only the replacement operation in the calculation of the edit distance and finds an approximate matching between T and Pin constant-time on a 3D RMESH.

Department(s)

Computer Science

Keywords and Phrases

String matching, Approximate string matching, Reconfigurable mesh architectural, Parallel algorithms

Report Number

CSc-96-06

Document Type

Technical Report

Document Version

Final Version

File Type

text

Language(s)

English

Rights

© 1996 University of Missouri - Rolla, All rights reserved

Publication Date

1996-07-01

Download

Share

 
COinS