wow..!! Thanks alot Tushar..!! Your tutorials are always informative and are in detail. But the best part is that its easily explained and extremely easy to understand and implement... :)...
Great Job as Always. I did understood the Algorithm instantly, but struggled in the implementation. Can you give any tips to improve on the implementation part. Maybe something I need to do or something I might be doing wrong.
Wow! you have done a great job :) And is that reusing match count within the Z box is benefit will i get compare to brute force ?? if not how it is better than brute force ?
What happens if parent string is 'aaaaa' and we have to calculate the no. Of comparison then it should be 4+3+2+1 or we can say it is of the form n+n-1+n-2+....1 therefore it's complexity is On^2
+Tushar Roy - your explanation is great , but it would be really good if you can give some context about the algorithm , like how difficult it is , etc.
Excellent tutorial. I have one question to ask. Why should we prepend the pattern to the string. Instead we can also compare while it is a different string
Honestly, it's not right. When you copy the values from Z-box to Z-box, you make a comparison for every number to find out whether it falls beyond the right boundary or not. Why these comparisons are not accounted for?
I am also wondering why its not counted in this video. Probably if we count that too, it should not go beyond linear time. But what will be the proof of that??
Yes, they should be counted, but that still makes the algorithm in linear time because when it falls in the right bounds, we will just copy the count, saving multiple comparisons from the first time. When it is out of bounds, we are going beyond the Z box, making new comparisons.
I think you are confused here because of the while in the for loop. Watchout that the while comparison is known and withing the Bounds (i.e 0-Left and R to Length at most). So it will not be n^2 complexity. If the while comparison was from 0 to N then it will be n^2
good explation of algorithm and code both. Generally doesn't find the code explanation easily so good job. I guess all u need to improve that use something much digital and clear then this white board that's all.
But why not just use a for that goes along the main text and looks for the pattern chars in sequence, and when a mismatch occurs, reset the index of where to look into in the pattern string. Why do all this work ?
You do realize this is a O(m*n) (O(m*(n-m) to be exact) comparison where m is the length of the pattern and n is the length of the string algorithm compared to Z algorithm's O(n) complexity right? You're doing a comparison for the full pattern at each index. I do not buy your statement that this performed better than the Z algorithm. I think you should double check your implementation of the Z algorithm
At this time stamp, we are at index 17 now since this character is in Z-box(notation used in video) we want to take its value from the previous position i.e from index 4, if we take its value 4 from the previous index(4), it means that a prefix of length 4 of the original string matches the suffix starting at index 17, but since the total length of string is only 18, the value can't be 4, since the suffix starting at index 17 can be of length 1 only. Hence the value is min(prev_value_taken, remaining length) i.e min(4, 18-17) = 1. Hope it helps
even the paid course don't teach you with this much perfection hats off to tushar for this and many other videos like this .
This video is absolutely perfect. Everything is explained very well from the fundamentals to the implementation part.
I spent so much time trying to understand this from someone else's the source code. Watching this cleared up all my confusions. Thanks!
Brother, I have started exploring String Algorithms few days back and , believe me , this is best resource I have found so far on the whole internet.
Thanks for such a wonderful explanation. This algo is one of the hardest as there are many variables you need to track and requires practice.
ok this is one of the few times where writing code is way more tougher than getting the logic..thanks btw great video
Tushar is a saver, it looks like other TH-camrs also watch Tushar's videos to clear their doubts.
One of the best explanation available on internet
String Theory has always been a mystery for me until just now!Cannot thank you more !
This is not called "String Theory"!!! That is a branch of physics.
It's still is a mystery to you and other physicists.
wow..!!
Thanks alot Tushar..!!
Your tutorials are always informative and are in detail. But the best part is that its easily explained and extremely easy to understand and implement...
:)...
Loved the explanation.. Thank you for the video.
we can use even lps(longest prefix suffix) array of appended string to find out the index of matching
Absolutely great! You made it very easy to understand the algorithm, thank you so much!!
I always like your videos, to the point no time wasting.
Best explanation , awesome teacher !!!
+Tushar Roy -great explanation as usual , clearly shows how well you understand.
excellent explaination, I understood it instantly
Excelent video, helped a lot
true
best video tutorial amazing Mr. Tushar.
Nicely explained
Thanks a ton :D Waiting for Aho - Corasick and Finite State Automation :D
8 months later im still alive but no video ;'{
4 years later, NO video
4yrs 10 months later, no video :(
8years now still no video
Excellent Tushar , you done it again.
Beautiful man.
Edit: Beautiful explanation, man
Amazing explaination !!11
Awesome explanation. Thank you very much
Great Explaination Sir
Great Job as Always. I did understood the Algorithm instantly, but struggled in the implementation. Can you give any tips to improve on the implementation part. Maybe something I need to do or something I might be doing wrong.
Very good explanation.Thanks Tushar.
Man!!!That's Amazing Explaination...Thank You:)
INFORMATIVE
Well Explained!!, Keep it up
Great explanation. Thanks!
Amazing explanation 😀
Great tutorial!
Thanks alot Tushar..!!
Wow! you have done a great job :) And is that reusing match count within the Z box is benefit will i get compare to brute force ?? if not how it is better than brute force ?
What happens if parent string is 'aaaaa' and we have to calculate the no. Of comparison then it should be 4+3+2+1 or we can say it is of the form n+n-1+n-2+....1 therefore it's complexity is On^2
+Tushar Roy - your explanation is great , but it would be really good if you can give some context about the algorithm , like how difficult it is , etc.
Nice explanation :) Very easy to understand compared to reading about it
It's very helpful and easy to understand :D Thanks u so much
helped a lot to understand the concept
you help me a lot, hope you upload more videos and I will always follow your channel~
Really Helpful . Thanks
Excellent tutorial. I have one question to ask. Why should we prepend the pattern to the string. Instead we can also compare while it is a different string
Excellent!
Great explanation !!!
Thankiu. Hope to wacth multiple matrix
What if the main string can consist of any utf8 character ?
How to choose a special character in such a case ?
Thank you!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!:)
Great tutorial as always.
Good job!
Good Job Brother.
Honestly, it's not right. When you copy the values from Z-box to Z-box, you make a comparison for every number to find out whether it falls beyond the right boundary or not. Why these comparisons are not accounted for?
I am also wondering why its not counted in this video. Probably if we count that too, it should not go beyond linear time. But what will be the proof of that??
Yes, they should be counted, but that still makes the algorithm in linear time because when it falls in the right bounds, we will just copy the count, saving multiple comparisons from the first time. When it is out of bounds, we are going beyond the Z box, making new comparisons.
I think you are confused here because of the while in the for loop. Watchout that the while comparison is known and withing the Bounds (i.e 0-Left and R to Length at most). So it will not be n^2 complexity. If the while comparison was from 0 to N then it will be n^2
Thank you very much !
As always great
Awesome!
Minor issue at 11:48 shouldn't it be greater than or equal to 1? Great video though!
what is the condition used at this timestamp? I did not understand. Could you please exlain?
Yaa, it should be greater than or equal to 1
Thanks alot bro!!! Such a great explanation of the algorithm :)
Thank you!
Awesome bro.....,
thanks a lot tushar, it really helped
Really great explanation. Thank you very much for the effort to explain it clearly!
nice explanation :)
Thanks Tushar
Hey Tushar ,
Great videos and explanation . Keep up the good work !
Do you have a video tutorial created for Sliding Window algorithm as well ?
You rock! Thank you!
at 21:04 time it will go the if condition because k is not greater than right but it is equal to right
good explation of algorithm and code both. Generally doesn't find the code explanation easily so good job.
I guess all u need to improve that use something much digital and clear then this white board that's all.
13:24 here we go digital
AHHH NICE EXPLANATIONS !!!!!
Thanks Tushar, great video! :) Can you explain Aho-Corasick in another one?
Thank you for the great explanation. I have one doubt though. We can do this algorithm even without $ right?
vhx.n ,o
No, there is a chance that the pattern maybe formed when we join the pattern and string.
Should Z[0] = the length of original string?
I don`t understand the O(m+n) part. I don`t understand its purpose.
Thankyou so much
on 11:16 when on index 13 the value of the Z array is 5, then 13+15 is crossing our Z box by 1 index. So, why we are not recalculating it again?
It will be great if anyone could help me out with this.
For user input how i will know that special character are not exist in the input given by user ? How can we solve this problem
sir please upload video of TRIE/ Prefix tree
Awesome algorithm sir :)
+Tushar Roy Please post LCA Queries sir
thank you :) very helpful
I'm your fan now
Thank you
helpful thx
Can i make table like kmp for z (pattern+$+text)?
Thank you very much. :)
But why not just use a for that goes along the main text and looks for the pattern chars in sequence, and when a mismatch occurs, reset the index of where to look into in the pattern string. Why do all this work ?
The index you are in the sequence have to reset to previous+1, so it is O(n²) time complexity
how you will compute Z Array for
Pattern P = caca and String = cacacacacacacacacaca. Please explain.
thank you
Scanner sc=new Scanner(System.in);
String s=sc.next();
String s1=sc.next();
int i;
for(i=0;i
i tried it codechef
how are you calculating the time complexity
mine
You do realize this is a O(m*n) (O(m*(n-m) to be exact) comparison where m is the length of the pattern and n is the length of the string algorithm compared to Z algorithm's O(n) complexity right? You're doing a comparison for the full pattern at each index. I do not buy your statement that this performed better than the Z algorithm. I think you should double check your implementation of the Z algorithm
When to use Z Algorithm and when to use KMP?
Thanks for this video but I did not understand at 11:48...Could you (or any one)please explain this condition?
At this time stamp, we are at index 17 now since this character is in Z-box(notation used in video) we want to take its value from the previous position i.e from index 4, if we take its value 4 from the previous index(4), it means that a prefix of length 4 of the original string matches the suffix starting at index 17, but since the total length of string is only 18, the value can't be 4, since the suffix starting at index 17 can be of length 1 only.
Hence the value is min(prev_value_taken, remaining length) i.e min(4, 18-17) = 1.
Hope it helps
what if my pattern or my text the '$' exist will the code still work fine?
Very Helpful! Thank you.
why we need the line right--; ?
He made a mistake at 10:04. It is not 17, it is 16.
Can anyone explain to me why do we do right - - in calculatez function.
Thanks in advance
Hope you reply, but if it's not, it's okay
while watching this video my brother (small haldi bilauwa) was beating me
plz speak at normal speed at starting of video.every thing else is too good
12:01
char[18] should be compared to char[5], not char[1]
Duy Dang correct
That's why he used l and r to specify where he can directly write or not. He did it
correctly.
great tutorial! would you mind putting subtitles, tho? xD
the guy probably speaks better than you
Who is here after today's Leetcode contest?