Knuth–Morris–Pratt (KMP) Pattern Matching Substring Search - First Occurrence Of Substring

Greatly explained, i saw a couple other videos but yours made me really understand it

KING 👑

I can tell coders for normal people. Normal people count 1, 2, 3, … Coders do not count, they calculate memory address offsets 0, 1, 2,…

So you want to find the location of each proper suffix which is also a prefix of the pattern?

explained very well thanks!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

It's a little misleading as to what part of the algorithm actually "saves work". Positive values in the KMP table force the algorithm to backtrack and try different parts of the match string p against s. Because the KMP table accounts for backtracking, the search through s can continue on after mismatches, without backtracking, as long as there are no entries in the KMP table. So even if the lookup table were completely empty, this offers a huge speedup

(volume - 10) + (repetition / 10) = watchable.

Very, very poorly explained.

Thanks you're awesome.

So far this is the first algorithm that made me stop and think for a while

Excellent explanation!

wow

I love his energy. Hard to loose focus.

why are you yelling bro?

Hi, what is the point in making an entry in the border table for the last character in the substring? As there cant be a mismatch that requires its use? Once you get to that point in the substring you'll either find a match and the algorithm terminates, or you find a mismatch and look at the border of the table[0...7]

thansk man

Top-notch content

Thank you~

Advance one to be recognized

Can we just concatenate, the first string and find the position of second string like if it exits?

Great Video,KMP is now crystal clear to me .Thanks !!!
Love from India♥

Unrelated but Donald Knuth's last name is pronounced like "Ka-Nooth" Great explanation, very clear.

you explained it so nicely

Brilliant explanation - certainly one of the best for the KMP algorithm. I like how you focus on the intuition behind the algorithm, as opposed to the traditional textbook approach. Have you considered writing a book on algorithms?

do they really think we'll be able to come up with this shit on our own in 30 minutes during a technical interview??

Perfect explanation. Thank you so much!

Terrific 🔥🔥

You are becoming my first choice for learning any new algorithm. Keep uploading👍 Hats off👏

Yay I think I understand it at last, thanks man!

Thanks! Very clear, detailed and energetic!!

Find the longest suffix which is also the prefix to save us from reverting the searching. Thanks!

it was a great help. Thanks man

what a bs video, you failed to utilize the best example of the algorithm... now you've literally matched from start to end

You've got the gift of explaining the concept

well done bro

Thank you from my heart.
I was about to give up on this algorithm, until I found this video, I appreciate this work so much.

just amazing explanation bro!

dude you need to chill when explaining

Leetcode easy????

never been so confused

I hope I am never asked this question, great explanation.

Amazing content. I've been going through your videos and they are so helpful!

Great explanation. I never got the intuition of why prefix/suffix works, but not anymore !

Pretty good explanation

Function to create the lpsArray according to explanation :-

public static void lpsArray(String s) {
int a[] = new int[s.length()];
a[0] = 0;
int i = 0;
for (int j = 1; j < s.length(); j++) {
if (s.charAt(j) == s.charAt(i)) {
i++;
a[j] = i;
} else {
if (i - 1 < 0) {
i++;
}
i = a[i - 1];
a[j] = i;
}
}
for (int x : a) {
System.out.print(x + " ");
}
}