codezonediitj / pydatastructs

A python package for data structures and algorithms
https://pydatastructs.readthedocs.io/en/stable/
Other
202 stars 270 forks source link

Implementation of the Knuth-Morris-Pratt (KMP) string matching algorithm #403

Closed sjathin closed 3 years ago

sjathin commented 3 years ago

References to other Issues or PRs or Relevant literature

Fixes #400. This PR includes the implementation of KMP String matching algorithm.

Brief description of what is fixed or changed

The Knuth-Morris-Pratt algorithm also known as KMP is a string matching algorithm that turns the search string into a finite state machine, then runs the machine with the string to be searched as the input string. Execution time is O(m+n), where m is the length of the search string, and n is the length of the string to be searched.[1]

codecov[bot] commented 3 years ago

Codecov Report

Merging #403 (fff59fe) into master (0dd2c03) will increase coverage by 0.043%. The diff coverage is 100.000%.

@@              Coverage Diff              @@
##            master      #403       +/-   ##
=============================================
+ Coverage   98.574%   98.618%   +0.043%     
=============================================
  Files           25        26        +1     
  Lines         3297      3401      +104     
=============================================
+ Hits          3250      3354      +104     
  Misses          47        47               
Impacted Files Coverage Δ
pydatastructs/strings/__init__.py 100.000% <100.000%> (ø)
pydatastructs/strings/algorithms.py 100.000% <100.000%> (ø)
pydatastructs/linear_data_structures/__init__.py 100.000% <0.000%> (ø)
pydatastructs/linear_data_structures/algorithms.py 99.715% <0.000%> (+0.061%) :arrow_up:

Impacted file tree graph

czgdp1807 commented 3 years ago

Thanks for the PR. Left some suggestions.

czgdp1807 commented 3 years ago

Thanks @sjathin for this.