W-Period Technique for Parallel String Matching
S. Viswanadha Raju, A. Vinaya Babu, G.V.S. Raju, K. Reddy Madhavi · 2007
In this paper, we present new approach for parallel string matching. Some known parallel string matching algorithms are considered based on duels by witness which focuses on the strengths and weaknesses of the currently known methods. This has applications such as string databases, Information Retrieval and computational biology. The new ‘divide and conquer’ approach has been introduced for parallel string matching, called the W-period, which is used for parallel preprocessing of the pattern and has optimal implementations in a various models of computation. The idea, common for every parallel string matching algorithm is slightly different from sequential ones as Knuth-Morris-Pratt or Boyer-Moore algorithm. Key words: Divide and conquer, duel, PRAM, string matching, W-period