Knuth-Morris-Pratt algorithm for String Matching

Author: Daman Daanna

Reference:
Thomas H Cormen(c2001). “Section 32.4: The Knuth-Morris-Pratt algorithm”. introduction of Algorithms(Second ed.). Cambridge,Mass.:MIT Press；Boston, Mass.: McGraw-Hill. ISBN9780262032933 (hbk., MIT Press).

[Vortigon]

Best explanation I have seen so far - I love the 6 - 2 = 4 explanation... not a single video other than yours has explained that so clearly and it helped to understand it much better!!

[butterflyninja]

THANK YOU SO MUCH FOR YOUR EXPLANATION. Your explanation so simple and easy to understand. I've been trying to understand this algorithm for 3 months, with your explanation, I can understand it in one night.

[BasselElBizri]

From the deep bottom of my heart ! THank you!! NO ONE in my school could explain it much easier !!!

[arbazgillani]

It is the complete explanation with perfect visuals. It saved me.

[scottmartin]

This is the best explanation I have found anywhere of this. Thank you

[Tinyxtina]

thank you, your explanation and visuals helped a lot. Best video on youtube explaining KMP.

[shwetankgupta]

It is the best video on KMP algorithm. @Dana Thanks for uploading and Happy Teachers Day :)

[hepichepic]

You have an amazing calm voice. Also you explain the algorithm so clear and simple. Thank you !

[johnathanho]

You did a marvelous job in explaining the algorithm! Even better than my professor XD Thanks so much

[shanukumar]

Very easy explanation. Thank you miss. Good work.

[chawza]

what is the prefix function? what does it relate with the partition table?

[polyroguegames]

there are quite a few videos out there attempting to explain KMP, all in broken English or just by running through nonsensical, bloated pseudocode. This video was a pleasant surprise, thank you so much. I thought I'd never understand how it works.

[AndyD]

At first, I was disappointed you didn't have a thick Indian accent but I think I can get used to this.

[lelouchlamperouge]

question

if the prefix table is zero based index?
what would be the q shift formula?

[rajbirs]

a complex task made easy!!, thanks for uploading

[SajithJohnSam]

Nice visualisation, great stuff Dana.. :) Too good
But is it proper suffix of Pq or suffix Pq ?

[peduran]

"Shift the pattern to the right to -0 two times" at 5.02. What does that mean? You cant shift something -0

[wiredauto]

THANKS A LOT I AM FROM KOREA I WANT TO CONQUER ALGORITHM. YOU ARE MY SAVIOR!!! I

[TheSalvation]

Hi Very nice explanation. I have one doubt at 4:35 and 5:22. When last character of pattern is not matching, we are accessing 6th element of prefix table. I dont see in this example uses 7th element of prefix table. So if it is not required at all can we just do not calculate it. This will reduce time complexity of creating prefix table by 1.

[Justinaccd]

8/58 comments here on her voice. Ya bunch of creeps...

Thanks for the vid! Very helpful visualization.