Knuth–Morris–Pratt(KMP) algorithm

[sjathin]

Description of the problem

Implement a string matching algorithm - Knuth–Morris–Pratt

Example of the problem

Input

1. string = "njfsonqwertylksmfds"
2. subString = "qwerty"

Output

True

References/Other comments

This is the first string matching algorithm in the project, it would be good to have a design that allows to have multiple string matching algorithms.

References

1. ICS 161: Design and Analysis of Algorithms Lecture notes for February 27, 1996
2. Knuth–Morris–Pratt algorithm

[czgdp1807]

Thanks for opening the issue. I think the API can be as simple as, find_string(text, pattern, algorithm='kmp'). Then on the basis of the algorithm passed we can decide which non-public function to call to obtain the result. For this you can also see shortest path algorithms in graphs/algorithms.py. Let me know your thoughts.

[amonikag]

I would like to work on this issue. I'm a GSSoC participant, please assign this to me.

[czgdp1807]

Hi @amonikag this is not a GSSoC issue. Please pick some other issue. @sjathin will be working on this. Thanks.