Pattern Matching Algorithms

• Goal: Given text, find the occurrences of a pattern in it and return the locations of match. The project focuses on benchmarking the following:

  • KMP
  • Boyer Moore
  • Naive approach

• Tools/Libraries used (incremental):

  • cProfile
  • pycallgraph
  • graphViz
  • GUI valgrind for python

• Resources:

  • https://docs.python.org/2/library/profile.html
  • https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt
  • https://people.duke.edu/~ccc14/sta-663/AlgorithmicComplexity.html
  • http://pycallgraph.slowchop.com/en/master/