Cost Optimal String Matching Algorithm on Linear Arrays

K. Narula, R. Jaiswal, and P. Gupta (India)

Keywords

Parallel Algorithms, Word Periods, Linear Arrays, Shifts, KMP Matcher.

Abstract

In this paper the problem of finding all occurrences of a pattern string of m symbols in a text string of n symbols taken from some alphabets, m ≤ n, is considered. We have first suggested an improvement in the KMP MATCHER algorithm for pattern matching and then proposed its cost optimal parallel implementation on linear arrays using nm/2 processors. Finally we present an O(log n) time algorithm for pattern matching in case with m = O(n) and O(log n) period of the pattern.

Important Links:

• DOI:
• From Proceeding (368) Networks, Parallel and Distributed Processing, and Applications - 2002

Go Back