CFP last date
22 April 2024
Reseach Article

Applying Bi-Directional Search Strategy in Selected String Matching Algorithms

by Grishma Pandey, G. L. Prajapati
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 143 - Number 11
Year of Publication: 2016
Authors: Grishma Pandey, G. L. Prajapati
10.5120/ijca2016910474

Grishma Pandey, G. L. Prajapati . Applying Bi-Directional Search Strategy in Selected String Matching Algorithms. International Journal of Computer Applications. 143, 11 ( Jun 2016), 40-43. DOI=10.5120/ijca2016910474

@article{ 10.5120/ijca2016910474,
author = { Grishma Pandey, G. L. Prajapati },
title = { Applying Bi-Directional Search Strategy in Selected String Matching Algorithms },
journal = { International Journal of Computer Applications },
issue_date = { Jun 2016 },
volume = { 143 },
number = { 11 },
month = { Jun },
year = { 2016 },
issn = { 0975-8887 },
pages = { 40-43 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume143/number11/25124-2016910474/ },
doi = { 10.5120/ijca2016910474 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:46:09.570626+05:30
%A Grishma Pandey
%A G. L. Prajapati
%T Applying Bi-Directional Search Strategy in Selected String Matching Algorithms
%J International Journal of Computer Applications
%@ 0975-8887
%V 143
%N 11
%P 40-43
%D 2016
%I Foundation of Computer Science (FCS), NY, USA
Abstract

String matching is an important problem in computer science having several practical applications. In this paper, we apply bi-directional searching mechanism in exact string matching algorithms: Boyer Moore, Brute Force, Knuth- Morris Pratt, and Rabin Karp. Experiments show that this strategy leads to better efficiency of these string matching algorithm.

References
  1. Nimisha Singla, Deepak Garg,”String Matching Algorithms and their Applicability in various Applications”, International Journal of Soft Computing and Engineering (IJSCE), Volume-I, Issue-6, January 2012.
  2. Apostolico , A. and Giancarlo, R., The Boyer-Moore-Galil, String searching strategies revisited, SIAM Journal on Computing, Vol. 15, 1986, pp. 98-105.
  3. Charras,C., Lecroq, T. and Pehoushek, J.D., A very fast string matching algorithm for small alphabets and long patterns, in Proceedings of Combinatorial Pattern Matching, 1998, pp. 55-64.
  4. Amir A., Lewenstein M., and Porat E., Faster Algorithms for String Matching with K-Mismatches, Journal of Algorithms 50(2004) 257-275.
  5. Knuth D.E., Morris J.H., and Pratt V.R., Fast Pattern Matching in Strings, Journal of Computing, Vol.6, No.2, 1977.
  6. Rami H. Mansi, and Jehad Q. Odeh, "On Improving the Naïve String Matching Algorithm," Asian Journal of Information Technology, Vol. 8, No. 1, ISSN 1682-3915, 2009, pp. 14-23.
  7. Lecroq, T.,A, Variation on the Boyer-Moore algorithm, Theoretical Computer Science, Vol. 92, No. 1, 1992, pp. 119-144.
  8. Charras, C. and T. Lecroq, Hand Book of Exact String- Matching Algorithms, Publication 2004, First Edition, ISBN: 978-0-7546-64.
  9. Singla N., Garg D., String Matching Algorithms and their Applicability in various Applications, International Journal of Soft Computing and Engineering, ISSN: 2231-2307, Volume-I, Issue.-6, January 2012.
Index Terms

Computer Science
Information Sciences

Keywords

Boyer Moore Algorithm Brute Force Algorithm Knuth- Morris Pratt Algorithm Rabin Karp Algorithm