Research Article
Performance Analysis of Selected String Matching Algorithms based on Good Suffix and Bad Character Rule
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 140 - Issue 9 |
| Published: April 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, Tushar Jain . Performance Analysis of Selected String Matching Algorithms based on Good Suffix and Bad Character Rule. International Journal of Computer Applications. 140, 9 (April 2016), 28-37. DOI=10.5120/ijca2016909445
@article{ 10.5120/ijca2016909445,
author = { G.L. Prajapati,Abhijeet Singh Rathore,Bhavana Tanwar,Surbhi Bhadviy,Tushar Jain },
title = { 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 },
doi = { 10.5120/ijca2016909445 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2016
%A G.L. Prajapati
%A Abhijeet Singh Rathore
%A Bhavana Tanwar
%A Surbhi Bhadviy
%A Tushar Jain
%T Performance Analysis of Selected String Matching Algorithms based on Good Suffix and Bad Character Rule%T
%J International Journal of Computer Applications
%V 140
%N 9
%P 28-37
%R 10.5120/ijca2016909445
%I 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
- Boyer R.S., Moore J.S., 1977, a fast string searching algorithm. Communications of the ACM. 20:762772.
- 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 255300, Elsevier, Amsterdam.
- Crochemore, M., 1997. Offline serial exact string searching, in Pattern Matching Algorithms, ed. A. Apostolico and Z. Galil, Chapter 1, pp 153, Oxford University Press.
- Zhu R.F., Takaoka T., 1987, on improving the average case of the BoyerMoore string matching algorithm, Journal of Information Processing 10(3):173177.
- Smith P.D., 1991, Experiments with a very fast substring search algorithm, Software Practice & Experience 21(10):10651074.
- Horspool R.N., 1980, Practical fast searching in strings, Software Practice & Experience, 10(6):501506.
- Sunday D.M., 1990, a very fast substring search algorithm, Communications of the ACM. 33(8):132142
- The SMART tool used for execution of algorithms can be found at: http://www.dmi.unict.it/~faro/smart/.
Index Terms
Keywords