Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search)

Here is the link.

5:18 PM - 6:00 PM

I need to push myself hard to learn KMP algorithm in 14 minutes.

First 6 minutes video:

KMP Substring search
              0   1   2   3  4  5  6  7
text        a   b   c   b   c  g  l   x  --------. m

pattern   b   c   g   l   l  -> O(mn)

KMP algorithm can be completed in O(m + n) time complexity

KMP Substring search

text - abcxabcdabxabcdabcdabcy

pattern - abcdabcy


KMP Substring Search