Z Algorithm Z values

[@code-for-mars]

even the paid course don't teach you with this much perfection hats off to tushar for this and many other videos like this .

[@siddheshshinde4850]

This video is absolutely perfect. Everything is explained very well from the fundamentals to the implementation part.

[@shahinshahsavari1275]

I spent so much time trying to understand this from someone else's the source code. Watching this cleared up all my confusions. Thanks!

[@Nikhil-ov6sm]

ok this is one of the few times where writing code is way more tougher than getting the logic..thanks btw great video

[@satviktejas6085]

One of the best explanation available on internet

[@sanketneema286]

Tushar is a saver, it looks like other KZbinrs also watch Tushar's videos to clear their doubts.

[@Aditya-wj5gy]

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.

[@yogeshyogesh8789]

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.

[@abhisheksharma7056]

we can use even lps(longest prefix suffix) array of appended string to find out the index of matching

[@aashutoshagrawal5239]

Loved the explanation.. Thank you for the video.

[@shubhamk840]

best video tutorial amazing Mr. Tushar.

[@AGENTxxFURY]

Best explanation , awesome teacher !!!

[@saurabhsharma7123]

String Theory has always been a mystery for me until just now!Cannot thank you more !

[@shreyjain51]

This is not called "String Theory"!!! That is a branch of physics.

[@genuineprofile6400]

It's still is a mystery to you and other physicists.

[@shuangli5466]

excellent explaination, I understood it instantly

[@sanjeevacham2400]

Excellent Tushar , you done it again.

[@omprakashsharma9767]

I always like your videos, to the point no time wasting.

[@vijay_lakra]

Very good explanation.Thanks Tushar.

[@malharjajoo7393]

+Tushar Roy -great explanation as usual , clearly shows how well you understand.

[@keilamartinez7394]

Absolutely great! You made it very easy to understand the algorithm, thank you so much!!

[@tahanimachowdhury]

Thanks a ton :D Waiting for Aho - Corasick and Finite State Automation :D

[@Shawn9081]

8 months later im still alive but no video ;'{

[@adhishmalviya2408]

4 years later, NO video

[@muthojusaketh]

4yrs 10 months later, no video :(

[@jotsinghbindra8317]

8years now still no video

[@smartwork7098]

Beautiful man. Edit: Beautiful explanation, man

[@sgerodes]

Awesome explanation. Thank you very much

[@marcolunardi3630]

Excelent video, helped a lot

[@MrDirtzuke]

true

[@shekhar3027]

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... :)...

[@udaysabbisetty9509]

Man!!!That's Amazing Explaination...Thank You:)

[@shivampratapsingh2188]

Amazing explaination !!11

[@aniketsriwastva6345]

Great Explaination Sir

[@saqibmasood501]

Nicely explained

[@gandhijainamgunvantkumar6783]

Amazing explanation 😀

[@ankitm511]

Nice explanation :) Very easy to understand compared to reading about it

[@prashantkaushal4057]

at 21:04 time it will go the if condition because k is not greater than right but it is equal to right

[@savanmatariya7494]

Well Explained!!, Keep it up

[@quyenamba4556]

It's very helpful and easy to understand :D Thanks u so much

[@pramodprajapati9166]

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.

[@fruith_]

Thankiu. Hope to wacth multiple matrix

[@ankitkumar-et8ew]

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

[@KanagaveluSugumar]

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 ?

[@cm30tanaykulkarni14]

INFORMATIVE

[@ningwang8077]

you help me a lot, hope you upload more videos and I will always follow your channel~

[@glaucoa.9214]

Thanks alot Tushar..!!

[@saurabhv1]

What if the main string can consist of any utf8 character ? How to choose a special character in such a case ?

[@Nate-kw9by]

Great tutorial!

[@ketan_sahu]

Great explanation. Thanks!

[@srijonmuhtasim3669]

helped a lot to understand the concept

[@DeepakKumar-wu4dt]

Really Helpful . Thanks

[@harshitgangwar1426]

Good Job Brother.

[@malharjajoo7393]

+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.

[@venkatnarasimha1317]

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

[@sarthakbansal1303]

Great explanation !!!

[@mohit7717]

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

[@KittyMaheshwari]

Excellent!

[@ChinmayTerse]

Minor issue at 11:48 shouldn't it be greater than or equal to 1? Great video though!

[@pawantiwary2043]

what is the condition used at this timestamp? I did not understand. Could you please exlain?

[@pranaykanjolia9077]

Yaa, it should be greater than or equal to 1

[@BenevolentKhalluudi]

Really great explanation. Thank you very much for the effort to explain it clearly!

[@sheetal831]

Thanks alot bro!!! Such a great explanation of the algorithm :)

[@ranganroy8494]

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?

[@ranganroy8494]

It will be great if anyone could help me out with this.

[@juzhengzhang3059]

Should Z[0] = the length of original string?

[@dronelektron]

As always great

[@Vicky-pu5fw]

sir please upload video of TRIE/ Prefix tree

[@sauravsingh7216]

Awesome bro.....,

[@nwanzefranklin7777]

thanks a lot tushar, it really helped

[@markjethropacheco4546]

I don`t understand the O(m+n) part. I don`t understand its purpose.

[@ScramblerUSA]

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?

[@deepankarsingh7230]

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

[@sundeepb]

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.

[@pramodprajapati9166]

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

[@CryingMG]

Great tutorial as always. Good job!

[@biboswanroy6699]

I'm your fan now

[@edelfrefloresmamani4562]

nice explanation :)

[@dineshkumar-kz3nc]

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.

[@kaal_bhairav_24]

13:24 here we go digital

[@bishyankar2388]

Scanner sc=new Scanner(System.in); String s=sc.next(); String s1=sc.next(); int i; for(i=0;i

[@bishyankar2388]

i tried it codechef

[@bishyankar2388]

how are you calculating the time complexity

[@bishyankar2388]

mine

[@elllot_]

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

[@ninhtrinh8536]

Thank you very much !

[@mujahidansorimajid1524]

what if my pattern or my text the '$' exist will the code still work fine?

[@imyashdeepsharma]

Awesome algorithm sir :)

[@imyashdeepsharma]

+Tushar Roy Please post LCA Queries sir

[@singhalvikash]

Hey Tushar , Great videos and explanation . Keep up the good work ! Do you have a video tutorial created for Sliding Window algorithm as well ?

[@jithinbabu6902]

Thank you for the great explanation. I have one doubt though. We can do this algorithm even without $ right?

[@francineidesilva5310]

vhx.n ,o

[@madhankumar8463]

No, there is a chance that the pattern maybe formed when we join the pattern and string.

[@Inotaku]

why we need the line right--; ?

[@anurag6219]

AHHH NICE EXPLANATIONS !!!!!

[@lonandon]

When to use Z Algorithm and when to use KMP?

[@gigelfranaru]

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 ?

[@danielmitre]

The index you are in the sequence have to reset to previous+1, so it is O(n²) time complexity

[@martokalinov3733]

Thank you!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!:)

[@pawantiwary2043]

Thanks for this video but I did not understand at 11:48...Could you (or any one)please explain this condition?

[@mishramadhur]

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

[@sarwarjahan05]

Can i make table like kmp for z (pattern+$+text)?

[@gal1l1l-f7c]

Thanks Tushar, great video! :) Can you explain Aho-Corasick in another one?

[@durgeshdeep2544]

Thanks Tushar

[@rohitraj4394]

how you will compute Z Array for Pattern P = caca and String = cacacacacacacacacaca. Please explain.

[@vedicdutta2856]

Awesome!

[@subtlechords]

Thankyou so much

[@fruith_]

Hope you reply, but if it's not, it's okay

[@rahukdubey8138]

while watching this video my brother (small haldi bilauwa) was beating me

[@ritikbansal4851]

Can anyone explain to me why do we do right - - in calculatez function. Thanks in advance

[@shreyjain51]

He made a mistake at 10:04. It is not 17, it is 16.

[@SNM_23745]

thank you

[@edwardnjoroge5222]

You rock! Thank you!

[@somesome1315]

helpful thx

[@grev7794]

thank you :) very helpful

[@duydangdroid]

12:01 char[18] should be compared to char[5], not char[1]

[@deepalikhalkar1880]

Duy Dang correct

[@satishkumarpatra4896]

That's why he used l and r to specify where he can directly write or not. He did it correctly.

[@timothyfield6190]

Very Helpful! Thank you.

[@yuvraj2038]

Who is here after today's Leetcode contest?

[@FelipeRodrigues-lj1el]

Thank you!

[@omaryasser2308]

Thank you very much. :)

[@ep.jonnadula]

plz speak at normal speed at starting of video.every thing else is too good

[@hAsH_learn2code]

Thank you

[@jesperat]

he sounds really angry.