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!
@galaxyspaceandtime97222 жыл бұрын
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.
@deanwinchester869129 күн бұрын
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.
@shubhamsharma79344 жыл бұрын
Thanks for the amazing video this algorithm is quite complex to grasp but after watching you video it is cakewalk
@chaitanyamanas19173 ай бұрын
I could not sleep for 2 days not understanding how we chose K less than L in the mismatch case, *thank you*!!
@cw59483 жыл бұрын
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.
@mirshodmirjonov99713 жыл бұрын
thank you bro, believe or not I have spend one day to learn this algo and now I understand logic, thank you sir again
@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
@motivation97184 жыл бұрын
Great video man !!! Probably the most elaborated explanation on prefix function.
@fluentalgorithms48474 жыл бұрын
Thanks a lot!!
@Aman-gw7ro3 жыл бұрын
best explanation so far for kmp algo . Thanks a lot man for your efforts!!
@prashantkashyap171 Жыл бұрын
finally get it after wasting hours trying other videos. Quite good explanation
@sachinsingh19564 жыл бұрын
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.
@inderjeetyadav28103 жыл бұрын
Very nice and simple explanation of a complex algorithm like KMP. Loved it.👍👍
@makaronpaka8 ай бұрын
Thats an amazing explanation, thank you very much
@aryanchauhan66713 жыл бұрын
You are awesome bro. Great explanation. Thanks, may God bless u.
@TaniaSketches4 жыл бұрын
Just wonderfully explained... Went through so many high profile videos... But could not understand... Thank you do much... Finally clearly understood... Awsome video....
@beingnikhil1553 жыл бұрын
This video helped me to visualize the article on cp-algorithms. Otherwise it was very confusing to me Thanks
@priyankarrajgupta41983 жыл бұрын
You explained inner while loop max. iteration really well. That was the crux inorder to understand TC for prefix function. Thanks.
@KartikSingh-ew4mz3 жыл бұрын
Beautifully explained !! out of the box
@ishayadav45954 жыл бұрын
best explanation of prefix function on internet
@sitanshushukla18204 жыл бұрын
Best Explanation... Couldn't grasp from cp algorithms. ur vdo helped a lot
@sangeethasanthiya284 Жыл бұрын
Vera level explaination clear understanding super sir
@c.feifei79532 жыл бұрын
So well explained why j = failure[j -1] when the prefix-suffix match can't extend.
@sanskarmani90944 жыл бұрын
Explained as simply as possible. Love it.
@amitbendkhale6464 жыл бұрын
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)
@fluentalgorithms48474 жыл бұрын
Yup!
@amitbendkhale6464 жыл бұрын
@@fluentalgorithms4847 Crystal clear explanation, one of the best videos in algos, thanks!
@THEkarankaira4 жыл бұрын
best explaintation avaiable on the internet watch it patienlty helped a lot thnak u
@ritikagupta88474 жыл бұрын
Thorough explanation. Thanks a lot
@em_nikhil_0073 жыл бұрын
Thanks finally understood..
@harshraj22_4 жыл бұрын
Thanks . It was really helpful. Don't know why downvotes on codeforces.
@fluentalgorithms48474 жыл бұрын
I'm glad it was helpful! Thanks for watching!
@gaganganapathy92713 жыл бұрын
Great video, thanks buddy! :D
@harshareddy21794 жыл бұрын
Is the complexity you calculated for inner while loop amortized complexity of it?
@KaaiSpeaksHisMind3 жыл бұрын
Great work, thank you.
@nagarajhegde11974 жыл бұрын
Great work, great explanation
@anuragporwal46644 жыл бұрын
excellent work.
@TEJASKUMAR-qv6gw Жыл бұрын
best explanation
@ratanhegde92583 жыл бұрын
Thank you so much really helpful
@shashwattripathi7594 жыл бұрын
amazing explanation...just amazing :O
@fluentalgorithms48474 жыл бұрын
Glad you liked it!
@shivamkushwaha97304 жыл бұрын
Good explanation. People who dislike it, please write a reason for that. Don't just press the button.
@sanskarmani90944 жыл бұрын
How can we convert this algorithm so that we have no overlap between prefixes and suffixes? Meaning that lps[i]
@7687saurabh3 жыл бұрын
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.
@discussionforum71614 жыл бұрын
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 .
@sahilsharma29524 жыл бұрын
Really helpful. Thanks.
@sachin__ak2 жыл бұрын
why stop uploading videos we need more videos from you about different algorithms
@sanchitkumawat38034 жыл бұрын
awesome explanation bro
@sandipjana55534 жыл бұрын
awesome explanation
@smol_cute_penguin28 күн бұрын
what was this everything was over the head, have to watch again
@Prince-wv8nm2 жыл бұрын
GREAT
@ritikagupta88474 жыл бұрын
if the string is "aaaaaaaaaab" then the inner while loop will run ~n times the complexity will be O(n^2)??Am I correct?
@sachinsingh19564 жыл бұрын
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 .
@ritikagupta88474 жыл бұрын
@@sachinsingh1956 thank you
@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?
@VIVEKKUMAR-kt2ey3 жыл бұрын
Thanks bro
@amanr113143 жыл бұрын
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;
@ferfle Жыл бұрын
thx
@ayushsingh-hd5ld4 жыл бұрын
I am not able to understand the time complexity part
@samvidhaansingh1453 Жыл бұрын
Toughest topic yet.
@shubhamk8404 жыл бұрын
why does this video has so less views.
@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 ?