期刊名称:International Journal of Computer Science and Network Security
印刷版ISSN:1738-7906
出版年度:2007
卷号:7
期号:9
页码:162-165
出版社:International Journal of Computer Science and Network Security
摘要: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.
关键词:Divide and conquer; duel; PRAM; string matching; W-period