Call for Paper - August 2019 Edition
IJCA solicits original research papers for the August 2019 Edition. Last date of manuscript submission is July 20, 2019. Read More

Performance Analysis of Selected String Matching Algorithms based on Good Suffix and Bad Character Rule

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2016
Authors:
G.L. Prajapati, Abhijeet Singh Rathore, Bhavana Tanwar, Surbhi Bhadviy, Tushar Jain
10.5120/ijca2016909445

G L Prajapati, Abhijeet Singh Rathore, Bhavana Tanwar, Surbhi Bhadviy and Tushar Jain. Article: Performance Analysis of Selected String Matching Algorithms based on Good Suffix and Bad Character Rule. International Journal of Computer Applications 140(9):28-37, April 2016. Published by Foundation of Computer Science (FCS), NY, USA. BibTeX

@article{key:article,
	author = {G.L. Prajapati and Abhijeet Singh Rathore and Bhavana Tanwar and Surbhi Bhadviy and Tushar Jain},
	title = {Article: Performance Analysis of Selected String Matching Algorithms based on Good Suffix and Bad Character Rule},
	journal = {International Journal of Computer Applications},
	year = {2016},
	volume = {140},
	number = {9},
	pages = {28-37},
	month = {April},
	note = {Published by Foundation of Computer Science (FCS), NY, USA}
}

Abstract

String matching is a problem where a pattern is to be searched within a text. In this paper, we study about selected string matching algorithms which compute shifts; based on good suffix rule and/or bad character rule or their variations. Algorithms are compared on the basis of their execution time for different data sets; those differ on patterns and alphabet sizes. Finally, we present a summary for the selection of these algorithms in different applications, based on the experimental results obtained.

References

  1. Boyer R.S., Moore J.S., 1977, a fast string searching algorithm. Communications of the ACM. 20:762­772.
  2. Aho, A.V., 1990, Algorithms for finding patterns in strings. in Handbook of Theoretical Computer Science, Volume A, Algorithms and complexity, J. van Leeuwen ed., Chapter 5, pp 255­300, Elsevier, Amsterdam.
  3. Crochemore, M., 1997. Off­line serial exact string searching, in Pattern Matching Algorithms, ed. A. Apostolico and Z. Galil, Chapter 1, pp 1­53, Oxford University Press.
  4. Zhu R.F., Takaoka T., 1987, on improving the average case of the Boyer­Moore string matching algorithm, Journal of Information Processing 10(3):173­177.
  5. Smith P.D., 1991, Experiments with a very fast substring search algorithm, Software Practice & Experience 21(10):1065­1074.
  6. Horspool R.N., 1980, Practical fast searching in strings, Software ­ Practice & Experience, 10(6):501­506.
  7. Sunday D.M., 1990, a very fast substring search algorithm, Communications of the ACM. 33(8):132­142
  8. The SMART tool used for execution of algorithms can be found at: http://www.dmi.unict.it/~faro/smart/.

Keywords

Good Suffix Rule, Bad Character Rule, Boyer Moore Variations, String Matching Problem, Performance Analysis.