Research Article

Applying Bi-Directional Search Strategy in Selected String Matching Algorithms

by  Grishma Pandey, G. L. Prajapati
journal cover
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 143 - Issue 11
Published: Jun 2016
Authors: Grishma Pandey, G. L. Prajapati
10.5120/ijca2016910474
PDF

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 },
                        year    = { 2016 },
                        volume  = { 143 },
                        number  = { 11 },
                        pages   = { 40-43 },
                        doi     = { 10.5120/ijca2016910474 },
                        publisher = { Foundation of Computer Science (FCS), NY, USA }
                        }
                        %0 Journal Article
                        %D 2016
                        %A Grishma Pandey
                        %A G. L. Prajapati
                        %T Applying Bi-Directional Search Strategy in Selected String Matching Algorithms%T 
                        %J International Journal of Computer Applications
                        %V 143
                        %N 11
                        %P 40-43
                        %R 10.5120/ijca2016910474
                        %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
  • 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.
  • Apostolico , A. and Giancarlo, R., The Boyer-Moore-Galil, String searching strategies revisited, SIAM Journal on Computing, Vol. 15, 1986, pp. 98-105.
  • 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.
  • Amir A., Lewenstein M., and Porat E., Faster Algorithms for String Matching with K-Mismatches, Journal of Algorithms 50(2004) 257-275.
  • Knuth D.E., Morris J.H., and Pratt V.R., Fast Pattern Matching in Strings, Journal of Computing, Vol.6, No.2, 1977.
  • 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.
  • Lecroq, T.,A, Variation on the Boyer-Moore algorithm, Theoretical Computer Science, Vol. 92, No. 1, 1992, pp. 119-144.
  • Charras, C. and T. Lecroq, Hand Book of Exact String- Matching Algorithms, Publication 2004, First Edition, ISBN: 978-0-7546-64.
  • 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
No index terms available.
Keywords

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

Powered by PhDFocusTM