An Elementary Algorithm for Pattern Matching

IJCSEC Front Page

Abstract:
A string matching algorithm aims to find one or several occurrences of a string within another. String matching is a classical problem in computer science. Our approach presents an elementary and efficient algorithm. First, we find some index values of pattern of length m from text T, the algorithm returns the position of the first character of the desired substring in the text. In second phase it matches whether the substring at this index value matches the actual pattern P. The algorithm works in linear time, if the number of occurrences of the pattern in a string is very less.

Keywords: Pattern matching, Time complexity, String length.

References:

  1. Wikipedia The free Encyclopedia en.wikipedia.org/wiki/String_searching_algorithm.
  2. Thomas H Corman, Charles E. Leiserson, Ronald L. Rivest & Clifford Stein “Introduction to Algorithms- String matching”, EEE Edition, 2nd Edition, Page no 906-907.
  3. Alberto Apostolico and ZviGalil, “ Pattern Matching Algorithms” Published in Oxford University Press, USA, 1st edition, May 29, 1997.
  4. Rahul M, Diwate B, Satish J, Alaspurkar, “ A. Study of Different Algorithms for Pattern Matching”, International Journal of Advanced Research in Computer Science and Software Engineering. 2013; 3(3):1–8.
  5. Al-Mazroi A, Rashid NA, “A Fast Hybrid Algorithm for the Exact String Matching Problem” American Journal of Engineering and Applied Sciences. 2011; 4(1):102–07.
  6. Boyer RS, Moore JS, “A fast string searching algorithm”, Communication of the ACM. 1977; 20(10):762–72.
  7. http://www.cs.utexas.edu/~moore/best-ideas/string-searching/index.html.
  8. Shivaji SK, Prabhudeva S, “Plagiarism Detection by using Karp-Rabin and String Matching Algorithm Together”, International Journal of Computer Applications. 2015; 116(23):1–5.
  9. Gope AP, Behera RN, “A Novel Pattern Matching Algorithm in Genome Sequence Analysis”, (IJCSIT) International Journal of Computer Science and Information Technologies.2014; 5(4):5450–57.
  10. http://cs.indstate.edu/~kmandumula/presentation.pdf.