An Enhanced Boyer-Moore Algorithm for WorstCase Running Time

Manjit Jaiswal ., Dr. Nilay Khare .


This article adderesses the exact string matching problem which consists in finding all occurrences of a given pattern in a text.It is an extensively studied problem in the field of computer science mainly due to despite its popularity in diverse area of application such as cluster computing, image and signal processing, speech analysis and recognition, information retrieval, data compression,computational biology,intrusion detection and virus scanning detection.In the last decade several new algorithm has been proposed.In this paper we compares all improved of the Boyer-Moore algorithm with my enhanced Boyer-Moore algorithm practically and theoretically result.It is not only generate the largest distance but also produces the minimum shifting and frequency of comparisons steps.By this enhanced algorithm we can reduce the number of comparisons frequency and number of shifting steps during the searching process.Moreover result of this enhanced Boyer-Moore algorithm reveals the efficiency is higher than of previous improved Boyer-Moore algorithms and time complexity is reduced in the concept of worst case analysis and lower than BM algorithm.Our enhanced algorithm 16% boost-up than previous improved Boyer-Moore algorithm when executed on the CPU.This enhanced Boyer-Moore algorithm can be plays an important role in finding extremely fast genetic moleculer and complex sequence pattern of interested database alignment of DNA.

Full Text:



  • There are currently no refbacks.