Abstract—The string matching problem occupies a corner stone in many computer science fields because of the fundamental role it plays in various computer applications. Thus, several string matching algorithms have been proposed and applied in many applications, information retrieval, editors, internet searching engines, firewall interception and searching nucleotide or amino acid sequence patterns in genome and protein sequence databases. Several important factors are considered during the matching process such as the number of character comparisons, number of attempts and the consumed time. This research proposes a hybrid exact string matching algorithm by combining the good properties of the Quick Search and the Skip Search algorithms to demonstrate and devise a better method to solve the string matching problem with higher speed and lower cost. The hybrid algorithm was tested using different types of standard data set. Regardless of pattern lengths, the proposed hybrid algorithm provides better outcomes and better reliability compared with the original algorithms in terms of number of character comparisons and number of attempts. Additionally, the hybrid algorithm produced better quality in performance through providing less time complexity for the worst and best cases comparing with other hybrid algorithms.
Index Terms—Character comparisons, amino acids search, exact pattern matching.
Mustafa Abdul Sahib Naser is with the Al-Mansour University College Baghdad, Iraq.
Nur'Aini Abdul Rashid is with the currently the Deputy Dean of Academic and Students Development in School of Computer Sciences, Universiti Sains Malaysia.
Mohammed Faiz Aboalmaaly is with the interested in several areas of research such as multimedia conferencing, mobile ad-hoc network (MANET), pattern matching and parallel programming.
Cite: Mustafa Abdul Sahib Naser, Nur'Aini Abdul Rashid, and Mohammed Faiz Aboalmaaly, "Quick-Skip Search Hybrid Algorithm for the Exact String Matching Problem," International Journal of Computer Theory and Engineering vol. 4, no. 2, pp. 259-265, 2012.
Copyright © 2008-2024. International Association of Computer Science and Information Technology. All rights reserved.
