KMP algorithm | Pattern search algorithm | string search algorithm

[@mayank_upadhyay_19]

Actually, I was not expecting to understand much from video, but surprisingly it made the concept more clear than any other.

[@JaiPrakash-ku7it]

This was the third time, trying to understand the KMP in last one year. And finally got it. Thanks man! Great work.

[@techdose4u]

Welcome :)

[@NAVEENKUMAR-uj7xe]

Same case @jai i dont know why It was so confusing ...🤔

[@fraisespasmures9683]

Thankksss a lot for this video. I've watched 3 videos trying to understand this algo you're the first one to achieve it with very clear explanations and revelent example. Thanks man

[@om23999]

Best explanation, I have already watched 3 videos but none of it could give me as much clarification as this video did .

[@techdose4u]

Great :)

[@adityasikarwar7090]

I am trying understand the from last 4 hours , I read article at gfg but don't get get whole clarity and also watch many videos on ytube but don't understand complete working, But after watching this video I am completely confident about working of algorithm. Thanks sir ❤

[@techdose4u]

welcome :)

[@anirbanpal9432]

Best explanation, I'll be honest before watching it I have already watched 3 videos and 2 articles, but none of it could give me as much clarification as this video did. Thanks @Tech Dose

[@techdose4u]

Welcome :)

[@inFamous16]

Also refer Abdul Bari Sir's channel

[@debanjanchakraborty9946]

The explanation is best in short time

[@techdose4u]

Thanks :)

[@sureshdoodler]

most underrated channel

[@agnivashil4130]

still the best explaination found till now....!

[@techdose4u]

Thanks :)

[@shivangitiwari2485]

hands down. best video on KMP

[@diveshrajput572]

Very much helpful rather than other videos

[@techdose4u]

Thanks :)

[@jyotikumari-lp1qh]

best video of KMP thank you sir👏

[@techdose4u]

Welcome :)

[@anurag6219]

Trying to get this algo once more in a coding career of 5 years. will comment again whenever i will try again

[@techdose4u]

woww. cool

[@Dee_Rai]

You are doing a great job. Learning alot from your videos.

[@techdose4u]

Thanks :)

[@devraj-2310]

I watched 3 videos previously... but this time I got the idea....... thankYou sir...

[@katilak1827]

Mind-Blowing Man, You are just Awesome!

[@techdose4u]

Thanks :)

[@lambar0]

love the development of intuition ....that is the key

[@nanditmaheshwari1363]

Best video for KMP!!

[@sarthakkumar856]

As always you have got the best explanation on youtube. Thank you so much for making this subject easy❤

[@renon3359]

You definitely deserve much more likes and subscribers brother. Great content.

[@techdose4u]

Thanks

[@shourabhpayal1198]

Greatest of all time

[@techdose4u]

🤗

[@kanchidoshi6907]

Thanks for the video. can you pls explain how would traversal work in case text='aaaaab' and pattern ='aaab'?

[@RupamSasmalYt]

Very easy explanation, Thank u♥

[@techdose4u]

Welcome :)

[@rishabhkumar8115]

thanks for this video...you deserve this...man

[@sunwoodad]

From the above example, text: "abx abc abc aby", pattern: "abc aby" You said, when 'y' of pattern doesn't match with 'c' at text, we need to move the pattern pointer back until finding 'c', so we can stop at "abc" at pattern and move forward. I think it's wrong. I mean it's okay at above example. But, what if the text is "abx abc dec def", pattern: "abc def" ? When pattern sees 'f' doesn't match to 'c', the pointer of pattern will move back until finding 'c', but "dec" of text and "abc" at pattern doesn't match. And it will eventually determine it found the pattern from the text, but it didn't.

[@harsha-kiran]

Either use finite state automata or while matching current charcter when moving backwwrd on pattern, check whether the pattern from the start matches too

[@ankuradhey]

In pattern "abc def" there is no longest suffix which has matching prefix, so pattern search would start from first index of pattern string and it would result into a non match. Watch complete video in which there is a LPS array is created.

[@Bakasta170]

I am also not getting this even after watching full video

[@John83118]

Such an outstanding job! I recently enjoyed a similar book, and it was an absolute masterpiece. "Game Theory and the Pursuit of Algorithmic Fairness" by Jack Frostwell

[@WrongDescription]

Best explanation!!!! Thanks a lot!

[@girikgarg8]

@Tech Dose Can you make a video on Boyer Moore Searching algorithm also? It's there in Love Babbar sheet

[@shreyjain51]

This channel will become big one day!!!

[@techdose4u]

Thanks shrey :)

[@kr_ankit123]

Code for the above explanation in C++. Here haystack is text and needle is pattern to be matched. Kindly refer it. class Solution { public: int strStr(string haystack, string needle) { int n = needle.length(); vectorlps(n,0); int i=0; int j=1; while(j0 && needle[j]!=needle[i]) i = lps[i-1]; if(needle[i] == needle[j]) i++; lps[j]= i; j++; } i=0; j=0; // for(auto a:lps)cout

[@yashgajewar9019]

Great Explanation !!

[@abhinavkumar6344]

good explaination, Thank you

[@mainakmondal5228]

Very clear explanation...thanks sir...

[@anonymoussloth6687]

I don't understand one thing. suppose we have a pattern like this: txt: a a a b a (and so on...) pat: a a a b b lps: 0 1 2 0 0 In this case, where there is a mismatch at the last a and b, I understand why pat is started at 0. because there is no prefix that is also a suffix at that point in the pattern. But why is the txt pointer not shifted back?? How can we be sure that if the pattern is just shifted one place to the right (like in the naive/brute force method) that we won't find a match? meaning: a a a b a ... a a a b b I know in this case it is not a match, but how can we be sure that this is the case always? My question basically is, in this algo, we have a i pointer that is iterating through the txt and a j pointer that is iterating through the pat. when there is a mismatch, the j pattern is shifted back a certain amount (which i understand why) but the i pointer is not shifted at all. THIS is what I don't understand. j pointer is shifted based on if there is a prefix that is also a suffix and that makes sense. But i dont understand why the i pointer is not shifted REGARDLESS of whether a prefix is found or not.

[@khatrinitish]

I have same query

[@mahipalsingh-yo4jt]

Great explanation..!!!!!!!!!

[@techdose4u]

Thanks :)

[@sharanpreetchadha3579]

Sir , please make video on Boyer Moore algo , there is no good video about it on the net

[@techdose4u]

Noted :)

[@EinstienJr]

KING!

[@neilteng4161]

Why dont we need to take care of the mode when we subtract the first character and add the last one?

[@ghumakkad_yogi]

Please make video on kmp search also

[@techdose4u]

This is KMP search itself. I have just written sublist search. Both are same.

[@ghumakkad_yogi]

@@techdose4u okkk

[@nidhiprakash5084]

Can u please give the playlist name in the description too?

[@techdose4u]

Sure I will

[@ALEEMKHAWAR1]

you are just awesome.

[@poorbidalal]

Best One!

[@sharuk3545]

if string abmnbc then Longest PS is 1 but in yout logic its 0

[@ayushshukla2655]

also explain with code please !

[@JayantiChowdhury-x8u]

Why we are not moving i back to previous + 1 position?

[@RomanEmpire29]

great explanation thanks a lot

[@rankushvishwakarma5658]

Good job sir!

[@techdose4u]

Thanks :)

[@statusdeveloperss1234]

super bro

[@vaalarivan_p]

3:16 - 5:25

[@AniketSomwanshi-ll7mz]

Can you tell me how creating the LPS array is O(n) and no quadratic?

[@rithikraj1813]

Why everyone waste 5-10 mins in brute force 🤔🤔

[@techdose4u]

I shouldn't 😅

[@prakhargupta3949]

thank you

[@akshatchouhan5199]

Can you please provide java code for this algo

[@devmahad]

thanks :)

[@techdose4u]

welcome :)

[@protyaybanerjee5051]

Which software/hardware do you use to whiteboard ?

[@bharatkumar-be9ki]

This video is really confusing because you are overwriting everything. Nothing seems making sense. First you should tell the logic and then the algorithm.

[@prakashpratapsingh7323]

Great explanation, but I wanna ask whether u were the one in apna college for kmp algorithm. That video has the worst explanation.

[@techdose4u]

Thanks. I am only on Techdose and no other platform.

[@satishshingade8514]

u should take different examples .. everything else was great

[@akshatjain6854]

This is really confusing!

[@Bakasta170]

shi me yaar ;(

[@tanishasethi7363]

Ikr

[@Masarap1959]

Can you tell its background?

[@techdose4u]

What background??

[@Masarap1959]

Drawback and application of Sublist?

[@spetsnaz_2]

@@Masarap1959 I think it uses an LPS array, so extra space is used...This is the drawback I see