Knuth-Morris-Pratt (KMP) algorithm | String Matching Algorithm | Substring Search

Visual presentation of KMP substring search and LPS array computation with developing the logic for code. Includes several easy to understand examples.
- Knuth Morris and Pratt algorithm - substring search - Pattern Matching
- Brute force naive approach with example , worst case example and time complexity explanation
- how to improve brute force technique and come up with the KMP algorithm
- how to compute the LPS array
- KMP search algorithm code building with examples
- LPS array code building with examples
- Time and space complexity analysis
- Application of KMP algorithm

Code link,

Mastering loops playlist,

Learn C programming playlist,

Website link,

My Programming channel in Tamil language,

[logicfirst]

In KMP search method while i<N-M+1 is given by mistake. It should be i<N. Thank you @Mohit Sinha
@Priyank Rastogi @KEK for pointing it out.

[anant]

This is beyond amazing. I have literally seen every KMP tutorial on youtube and despite the efforts of the creators, they suck. You rock.

[baluk]

by far the best i have seen on KMP .. not only it explains the concept of KMP but goes beyond to implement a working code and also reason's out every "if and else" condition to perfection in a simple easy to understand language... someone who watches this can write KMP code even if woken from sleep....

[shayaksarkar]

I literally struggled with this for 2 years. Each time I saw an explanation in the net, it made me even more scared of this algorithm, until I found this. This is literally awesome.

[nikhilkumar]

After banging my head on wall for 7 days straight, I'm now peacefully having a cup of tea. Thankyou ma'am 🙏

[algotorials]

when again stuck with algorithm first search for @Logic First, its worth the name.

[vishalmahavratayajula]

Where were you hiding these many days?

[parashar]

This is THE ONLY channel that has explained this complicated concept really well. Every other channel miserably failed in doing it. Bravo!

[a.m.]

What I like about this presentation is the absolute fluidity and flow - no discontinuity, no mumbling, no stuttering, clean and smooth without struggling to recall terminologies or memorize. Good video. 8.5/10.

[SurajYadav-bcid]

Best explanation of this KMP algorithm on YouTube and hell lot better than my college lecture. Thank you very much for making this concept crystal clear. I'm definitely gonna recommend your channel to my peers and juniors.

[srirampant]

This video needs more likes, seriously it is good unlike other videos the algorithm is properly explained instead of just displaying just the code . Thanks for explaining.

[adityanihalkumarsingh]

Very underrated video. KMP couldn't be clearer. Amazing job.

[fdvritp]

I don't comment often on videos, but I was really not getting the essence of KMP until now.
Thanks a lot, ma'am.
Really the best video on yt for KMP.

[durgaprasadkumar]

Better explanation found so far on youtube, you will have a great future. Please start uploading more Algo videos

[matrixtoogood]

Wow, the perfect video on KMP algorithm. Watched 5-6 videos from other YouTubers but nobody mentions all the small points important to understand KMP that you covered. Explanation of the LPS array and its usage was the best!

[munishthakur]

One of the best explanation of KMP that makes us reach it, by asking intuitive questions. Instead of directly telling us the KMP algo.

[akshayshah]

Coundn't find any better explanation than Work!

[compiler]

thank you very much, came here from backtobackswe as he did not explain the len=lps[len-1] part in calc. of lps array, must say i have never seen such crystal clear explanation, hope to see more of it. Thank You, you are doing a wonderful work for the community.

[rashmikiranpandit]

Thanks a ton for this invaluable clear n easy explanation, I can't thank enough!

[aditya]

THANK U SOO MUCH. YOU ARE THE BEST! No one explains such basics. I was amazed to see a video on application of GCD too. Thank you again!!!