Cost Optimal String Matching Algorithm on Linear Arrays

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


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


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:

Go Back