KMP algorithm | Pattern search algorithm | string search algorithm

Very much helpful rather than other videos

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

Which software/hardware do you use to whiteboard ?

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

u should take different examples .. everything else was great

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

Mind-Blowing Man, You are just Awesome!

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.

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

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

Greatest of all time

vector<int> lps(string s)
{
int n=s.size();
vector<int> ans(n,0);
ans[0]=0;
i=0;
int j=0;
for(j=1;j<n;j++)
{
if(s[i]==s[j])
{
i++;
}
else
{
while(i>0&&s[i]!=s[j])
{
i=ans[i-1];
}
}
ans[j]=i;
}
return ans;
}
bhaiya ye sahi hai khya please reply

great explanation thanks a lot

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

Can you please provide java code for this algo

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

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

Very clear explanation...thanks sir...

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

you are just awesome.

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();
vector<int>lps(n,0);
int i=0;
int j=1;
while(j<n){
while(i>0 && 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<<a<<endl;
while(i<haystack.size()){
while(j>0 &&j<n && needle[j]!= haystack[i]){
j = lps[j-1];
}
if(j<n &&needle[j] == haystack[i]){
j++;
}
i++;
if(j==n)return i-n;
}
return -1;
}
};

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

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

Very easy explanation, Thank u♥

thank you

The explanation is best in short time

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

Best explanation!!!! Thanks a lot!

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

tu AA ja MERE close le le thoda TECCHDOSE

THE C++ CODE OF THIS PROBLEM IS HERE
.....
.
.
..
.
..
.
.
..
...
.
.

....
.
.
.
.
..
.
..
..
...
KHUD SE KAR LE SAALE...SAB KUCH TO BATA DIYA

Best One!

Great Explanation !!

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 <3

most underrated channel

also explain with code please !

good explaination, Thank you

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

super bro

I feel lot of detailing is missed in this explaination. If some one wants a good understanding of kmp algo and how it works, please refere CodeNCode channel. Expected a better and thorough explaination sir.

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

Best video for KMP!!

hands down.
best video on KMP

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

KING!

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

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 ❤

thanks :)