KMP Algorithm Part 1 | Prefix Function

KMP is a linear time string matching algorithm where the logic or intuition behind this algorithms is very difficult to grasp. So in this video I can explain the concept behind the KMP algorithm, the prefix function. I explain the logic behind building the prefix function and discuss the time complexity as well as the pseudo code.

[@ariel-h6j]

This is the best explanation of prefix function of KMP algorithm Ive ever seen on youtube! Thank you so much for making this great video!

[@shubhamsharma7934]

Thanks for the amazing video this algorithm is quite complex to grasp but after watching you video it is cakewalk

[@chaitanyamanas1917]

I could not sleep for 2 days not understanding how we chose K less than L in the mismatch case, *thank you*!!

[@cw5948]

I appreciate you uploading this video. All the other videos I've looked at don't go into the mathematical rigor of how the PI prefix table is generated; they just give an algorithm which can be easily forgotten.

[@deanwinchester8691]

There is a lot of Garbage on KMP in youtube but this is Pure Gold. Was able to get the idea of finding L effectively from this. No other video was able to explain it this thoroughly.

[@mirshodmirjonov9971]

thank you bro, believe or not I have spend one day to learn this algo and now I understand logic, thank you sir again

[@galaxyspaceandtime9722]

The best explanation I have ever seen of lps array to get intuition rather than getting code only. Thank you so much for helping me.

[@motivation9718]

Great video man !!! Probably the most elaborated explanation on prefix function.

[@fluentalgorithms4847]

Thanks a lot!!

[@sachin__ak]

why stop uploading videos we need more videos from you about different algorithms

[@smol_cute_penguin]

what was this everything was over the head, have to watch again

[@beingnikhil155]

This video helped me to visualize the article on cp-algorithms. Otherwise it was very confusing to me Thanks

[@harshraj22_]

Thanks . It was really helpful. Don't know why downvotes on codeforces.

[@fluentalgorithms4847]

I'm glad it was helpful! Thanks for watching!

[@amitbendkhale646]

So, is the O(n) thing like this:
To get a drop of 't1' we should have moved earlier 'x1' steps in 'for loop' after the previous drop, and x1 >= t1 (otherwise drop wouldn't be possible);
So like Complexity of Drops is Sum(ti)

[@fluentalgorithms4847]

Yup!

[@amitbendkhale646]

@@fluentalgorithms4847 Crystal clear explanation, one of the best videos in algos, thanks!

[@inderjeetyadav2810]

Very nice and simple explanation of a complex algorithm like KMP. Loved it.👍👍

[@Aman-gw7ro]

best explanation so far for kmp algo . Thanks a lot man for your efforts!!

[@shashwattripathi759]

amazing explanation...just amazing :O

[@fluentalgorithms4847]

Glad you liked it!

[@enchantularity]

Hi I have the pattern "zyxwabacddfghabacdjhlop" . Won't pi function return all zero? There are two patterns , one prefix, another suffix .
Will your algorithm work here ?

[@anuragporwal4664]

excellent work.

[@samvidhaansingh1453]

Toughest topic yet.

[@haniariimaukloo3892]

why is pi of 8 equal to 1 and not 2? Ps: I'm referring to the last example

[@manusabuu]

I have same doupt

[@manusabuu]

How pi (7 ) =1?

[@TEJASKUMAR-qv6gw]

best explanation

[@amanr11314]

bro after much re-watching the video i still can't understand the line if(s[i]==s[pi[i-1]]) pi[i] = pi[i-1] + 1;

[@7687saurabh]

k denotes next longest string which is a proper prefix and a proper suffix for substring 0 to i. Shouldn't the value of k should simply be l-1? Its not obvious why it is pie(l-1) rather than l-1.

[@ferfle]

thx

[@Prince-wv8nm]

GREAT

[@charanrajueluri3196]

thank you so much. this is very easily understanded to me, previously i saw many videos they are not properly understanded to me but this video gave a clear picture about kmp longest prefix function

[@c.feifei7953]

So well explained why j = failure[j -1] when the prefix-suffix match can't extend.

[@makaronpaka]

Thats an amazing explanation, thank you very much

[@sanskarmani9094]

How can we convert this algorithm so that we have no overlap between prefixes and suffixes? Meaning that lps[i]

[@prashantkashyap171]

finally get it after wasting hours trying other videos. Quite good explanation

[@aryanchauhan6671]

You are awesome bro. Great explanation. Thanks, may God bless u.

[@harshareddy2179]

Is the complexity you calculated for inner while loop amortized complexity of it?

[@shivamkushwaha9730]

Good explanation. People who dislike it, please write a reason for that. Don't just press the button.

[@sangeethasanthiya284]

Vera level explaination clear understanding super sir

[@sachinsingh1956]

This is the best video i ever seen for kmp algo . you make kmp algorithm veri easy.
Please try to make more video just like it for other algos , so that we can learn any algo in deep easily.

[@priyankarrajgupta4198]

You explained inner while loop max. iteration really well.
That was the crux inorder to understand TC for prefix function.
Thanks.

[@TaniaSketches]

Just wonderfully explained... Went through so many high profile videos... But could not understand... Thank you do much... Finally clearly understood... Awsome video....

[@em_nikhil_007]

Thanks finally understood..

[@gaganganapathy9271]

Great video, thanks buddy! :D

[@THEkarankaira]

best explaintation avaiable on the internet watch it patienlty
helped a lot
thnak u

[@ayushsingh-hd5ld]

I am not able to understand the time complexity part

[@sitanshushukla1820]

Best Explanation... Couldn't grasp from cp algorithms. ur vdo helped a lot

[@ishayadav4595]

best explanation of prefix function on internet

[@ratanhegde9258]

Thank you so much really helpful

[@KartikSingh-ew4mz]

Beautifully explained !! out of the box

[@sanskarmani9094]

Explained as simply as possible. Love it.

[@KaaiSpeaksHisMind]

Great work, thank you.

[@ritikagupta8847]

Thorough explanation. Thanks a lot

[@VIVEKKUMAR-kt2ey]

Thanks bro

[@shubhamk840]

why does this video has so less views.

[@ritikagupta8847]

if the string is "aaaaaaaaaab" then the inner while loop will run ~n times the complexity will be O(n^2)??Am I correct?

[@sachinsingh1956]

O(1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 9) = O(19)
inner while loop run only one time for n times but in rest of case it will run only one time .

[@ritikagupta8847]

@@sachinsingh1956 thank you

[@sanchitkumawat3803]

awesome explanation bro

[@nagarajhegde1197]

Great work, great explanation

[@sandipjana5553]

awesome explanation

[@sahilsharma2952]

Really helpful. Thanks.

[@discussionforum7161]

This was a topic i thought to explain but after i seeing your video i think it's been done in a good way already .