Very nice and so simple explanation .somebody who not belong to software industry will also understand easily . keep posting these videos this really helps us .
Excellent Tushar! Now got the Rolling hash function :) And it is great that you are explaining about the real time application where it is used and its time complexities. It will also be great if you do explain about where it will fails as well as comparing with other equivalent algorithms which solve those failures at the end of the session.
I think this is wrong. You are not doing the required modular arithmetic to reduce the false positives. The method will work but this is not the complete algorithm. Someone should prove me wrong on this.
He has not used to the table size of the hash (the prime number here) anywhere. You will need to find the modulo of the final hash value, otherwise you will get strings which hash to values greater then the prime number, which clearly won't fit in the Hash Table
@Tushar please send us or post your patron link.. i cant keep learning without returning the immense value these lectures are providing! :) Thanks a lot and god bless you
Consider values of A=1, B=2, C=3 If we don't use prime numbers the hash value for ABC and BCA are ABC = 1+2+3=6 BCA = 2+3+1=6 Hash values are colliding causing the search to be inefficient.Instead if you used prime numbersABC = 1 * 3^0 + 2 * 3^1 + 3 * 3^2 = 1+6+27 = 34 BCA = 2 * 3^0 + 3 * 3^1 + 1 * 3^2 = 2+9+9 = 20Hash values are different and can be differentiated even if they contain same number of characters.
No, it does not guarantee that hash will never collide. If hash collides then we will check element by element and if it matches then only pattern is find otherwise not. This is the worst case if our hash function is not good and hase values colliding each other and indeed checking for each character and pattern is not found. o((n-m+1)*m ).
@@satadhi Generally multiplying with a large number ensures hashes won't collide but for understanding purpose it's advisable to take a small value number
can you plz make a video on aho corasick algorithm? i think its much more important than other multiple string searing algorithm as it takes linear time
Hey tushar, as per your algo we need to store mappings a=1,b=2,c=3 and so on. if input text contains 256 ASCII characters, maintaining mapping would be tough, I believe instead taking actual ASCII values of characters in pattern would be helpful. Again you have not told on what basis you have taken prime number(3), this is similar to converting string to base-3 number system. And in case of huge pattern string also if you take prime number as 101(as you told) it will make a huge number might overflow unsigned int boundaries as well. I believe using mod might be good. Also you did not told why 101 would be good, ie synonymous to converting number to base-101 number system. i belive taking smaller prime will lead to larger hash collisions and then lot of comparisons..
Good job! Thanks for your insights, I just have only one question, if the length of the pattern is getting really long, like more than 20 characters, then the hash value will become intolerable for most types.
Never mind. I believe I will need to continue the addition but increase the exponent. For example if the length is four, I will then add "+ n x 3^3" to the end of the calculation. Thanks.
There is a question, if the text string and the pattern string are consisted of Chinese characters and the two strings are longer a little, the hashcode may overflow so wrong results appear.As we known,Chinese characters have a large number of characters。
Thanks Tushar, very good explanation of Rolling hash concept. However, I have a question. Your hash could quickly cross the long int boundary for ascii characters if the pattern is long. Am I right? Would you not want to use a modulus operation to keep your hash value in check?
Hello tushar I appreciate your got work and effort.Please help me out if rabin carp can search for exact pattern or not. Suppose i am searching over a text file for the word "the" to calculate the frequency but it count the sub-string with the such as they them their. What logic can be added in the rabin karp so that it can go for exact match.
what if the string to be searched is too big ? lets say if the string is of size 10^5 and the string to be matched(present or not) is of size 10^4 then how will u calculate the hash ? pow(3,10^4) is overflowing here , so this algo doesn''t work when the string is too big ?
Thanks Tushar. If I understand this right - Brute-force time complexity is the same as this approach. So this algo excels on looks ups based on hashbased, and when hash calculation maps to collisions then this algo is no good. So do you think brute-force is better given the time complexities are same?
I tried hard but couldn't find your video for Brute Force string matching . Could you please give me the link here. Have an exam on Sunday. Would really appreciate it.
Code seems not working with large input such as ["aabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaa","baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"]. Both of them get the same initial hash, which is weird..
yes , i also commented this "isnt this approach will create overflow problem while calculating HASH ?? if pattern is more than 63 length.that to in best case . if we choose our prime 2. how can we compute 2^64 . looks like this approach has limitation , we should be using MOD also"
Paying 4 LPA college fees just to end up watching your free video lectures.
4 lpa??? Which college it might be?
@@pankajjahagirdar1278 Thapar University Bro
I didn't realize the power of rolling hash calculation unless applied it to longer text and patterns! Your 3-step calc is very good idea.
You're good. Keep helping us out when our professors won't and god will bless you!
understood perfectly after first example. May Allah reward you greatly for the work that you have done.
This is the first time I understand rolling hash functions. Great video! Keep up with the great work!
The rolling in and out part has been flawlessly explained. 👌 Thanks!
Sir you very much look like a famous UA-camr (THUGESH)
Even from a newbie perspective its easy-to-understand your videos, great initiative, thank you very much.
Very nice and so simple explanation .somebody who not belong to software industry will also understand easily . keep posting these videos this really helps us .
damn, this is 10x easier than trying to read the lemmas and proofs T_T
videos like these are good for knowing "how" things work. but proofs and lemmas help you to answer "why" this thing works
@@kumartatsat868 yea but you start ask knowing "how" things work then move on to "why" things work
Excellent Tushar! Now got the Rolling hash function :) And it is great that you are explaining about the real time application where it is used and its time complexities. It will also be great if you do explain about where it will fails as well as comparing with other equivalent algorithms which solve those failures at the end of the session.
""Hello friends my name is..."
its amazing
thank you for the crisp explanation, better and 10x note helpful than reading a boring book
The rolling hash calculation thing was really awesome
Very good explanation of the topic. Thank you for your effort. :)
which is ur country
u remember Andre Istvan from 3 IDIOTS :'p
@@nandkishorenangre8244 I remember Ishaan Nandkishor Avasthi from Taare Zameen Par :) LOL
@@piyushbhatia2324 Really ?!
@@nandkishorenangre8244
fuck u
Phenomenal tutorial, very clear. Thanks!
Best explanation ever seen..
Hats off..
Really detailed explanation which is understandable for all levels of students..Thank you
as always your explanation is one of the best ones I find in youtube, congrats!
Videos are really helpful. Keep up the good work Tushar
Very nice explanation.Please keep up the good work!
Thanks for the explanation, made me understand the operation of this algorithm, greetings from Peru.
which is ur country
Perú..... Regards my friend
Tushar, you nailed it man!
Awesome explanation. Easy to understood
awesome explanation .... you save my 8 marks ... thank you very much sir !!! 😊
I think this is wrong. You are not doing the required modular arithmetic to reduce the false positives. The method will work but this is not the complete algorithm. Someone should prove me wrong on this.
Yeah clearly, it is incomplete.
He has not used to the table size of the hash (the prime number here) anywhere. You will need to find the modulo of the final hash value, otherwise you will get strings which hash to values greater then the prime number, which clearly won't fit in the Hash Table
Even 3 years after your comment, I am still with you.
Same here..this does not work for large numbers..the has becomes 0 for large numbers . There should be some modulo operation wrt to prime numbers
Yes this is incomplete....
Very good explanation Tushar
Your video is always gold.
love your videos, they are very clear and useful!
Thanks a lot for the simple explanation!
@Tushar please send us or post your patron link.. i cant keep learning without returning the immense value these lectures are providing! :) Thanks a lot and god bless you
best video on this algortihm
Greatly explained sir👏🏻👍🏻
Why don't u use number of ascii values instead of a prime no.
This is clean and awesome explaination
GJ man you are my hero! you saved my exam! Thanks
Thankew so much your all videos help me alottttt.. You teach very well.. Thanx again sir
Very well explained. Thank you very much.
Nice video and explanation! Thank you!
This was extremely helpful, thanks!
Very nice explanation. Thanks!
Thank you understandable english! Thank you formsharing that knowledge! Helped me a lot!
Thank you for this video, you explained it very well
Thank you so much your videos are great and very helpful .
Great explanation - Thank you.
Thank you! You do a great job. When will you post the next algorithms?
Excellent explanation.
Thanks! Very clear explenation!
Really good Explaination!! Good Job :) thanks a ton!!
I don't understand why are we using prime numbers here....Why can't we simply add their ASCII values
Consider values of A=1, B=2, C=3
If we don't use prime numbers the hash value for ABC and BCA are
ABC = 1+2+3=6
BCA = 2+3+1=6
Hash values are colliding causing the search to be inefficient.Instead if you used prime numbersABC = 1 * 3^0 + 2 * 3^1 + 3 * 3^2 = 1+6+27 = 34 BCA = 2 * 3^0 + 3 * 3^1 + 1 * 3^2 = 2+9+9 = 20Hash values are different and can be differentiated even if they contain same number of characters.
Does this mean that there can never be hash collisions ?? Also, how can you prove that ?
No, it does not guarantee that hash will never collide.
If hash collides then we will check element by element and if it matches then only pattern is find otherwise not.
This is the worst case if our hash function is not good and hase values colliding each other and indeed checking for each character and pattern is not found.
o((n-m+1)*m ).
then how do you decide which hash function is better suited ?
@@satadhi
Generally multiplying with a large number ensures hashes won't collide but for understanding purpose it's advisable to take a small value number
best explanation sir, thank you so much
can you plz make a video on aho corasick algorithm? i think its much more important than other multiple string searing algorithm as it takes linear time
Very good video,thanks bro
Hey tushar, as per your algo we need to store mappings a=1,b=2,c=3 and so on. if input text contains 256 ASCII characters, maintaining mapping would be tough, I believe instead taking actual ASCII values of characters in pattern would be helpful. Again you have not told on what basis you have taken prime number(3), this is similar to converting string to base-3 number system. And in case of huge pattern string also if you take prime number as 101(as you told) it will make a huge number might overflow unsigned int boundaries as well. I believe using mod might be good. Also you did not told why 101 would be good, ie synonymous to converting number to base-101 number system. i belive taking smaller prime will lead to larger hash collisions and then lot of comparisons..
Please make more videos on String algorithms....thanks for the great videos....
Great Video.Keep on adding videos.
awesome !!! love your videos ...great work !!
bhai onek bhalo explanation :)
Thanks for the explanation!
Good job! Thanks for your insights, I just have only one question, if the length of the pattern is getting really long, like more than 20 characters, then the hash value will become intolerable for most types.
Could you please create a playlist on Searching algorithams? It is difficult to find other searching algo tutorials by you ?
Nice Explanation bro ...
You are the real hero !!!
Could you also provide links for videos that you already made like KMP in description
r u still uploading videos
sir tushar
Thanks you sir . Nice explanation
Awesome video but one doubt
what if we have to find multiple patterns and length of those multiple patterns vary?
Fantastic video..!! Thanks as always.. learning a lot. :-)
what if the substring length is like 100, the hash will exceed the integer even long limit
thanks! look forward more videos!
bhag chinese
Bro u r doing really grt job... I am preparing fr placements ur videos saved me frm going thru textbooks n all other stuff
Well Explained sir, you are great :P
I'm surprised that no one really checked that this algo will break if use value 3. Start with 4 and it works, with 3 it breaks.
this channel is quality
"we cannot do anything about it.":P great video buddy :)
gud 1 tushar.
This is great
thank you😀
The code will not work for large length of pattern. Overflow condition needs to be addressed
mate youre actually the goat
I'm a big fan. I love this video. If the pattern is longer than length of 3, what's the best way to adjust the hash calculation?
Never mind. I believe I will need to continue the addition but increase the exponent. For example if the length is four, I will then add "+ n x 3^3" to the end of the calculation. Thanks.
What do we say to the God of algorithms teaching
Thank you tushur roy
how to choose the prime number if the prime number is not given?
There is a question, if the text string and the pattern string are consisted of Chinese characters and the two strings are longer a little, the hashcode may overflow so wrong results appear.As we known,Chinese characters have a large number of characters。
***** The String class in Java has a method String.indexOf(), it just use the BF rather than KMP.
It is quite clear, but what if the string to be matched is really long? Hash value will be huge. Is there a way to optimize?
Ty, Keep up the good work!
Thanks Tushar, very good explanation of Rolling hash concept. However, I have a question. Your hash could quickly cross the long int boundary for ascii characters if the pattern is long. Am I right?
Would you not want to use a modulus operation to keep your hash value in check?
"if it goes beyond int or long size it will modulus itself"
I didn't get that. Would you please like to explain shortly ?
+Tushar Roy
Can u make a tutorial on Aho Corasick String Matching Algorithm Plz
*****
THNX
Hello tushar I appreciate your got work and effort.Please help me out if rabin carp can search for exact pattern or not. Suppose i am searching over a text file for the word "the" to calculate the frequency but it count the sub-string with the such as they them their. What logic can be added in the rabin karp so that it can go for exact match.
Good Explanation Thank you
goated explanation man
what if the string to be searched is too big ?
lets say if the string is of size 10^5 and the string to be matched(present or not) is of size 10^4 then how will u calculate the hash ? pow(3,10^4) is overflowing here , so this algo doesn''t work when the string is too big ?
but if we have to calculate hash for a very long pattern then we won't be able to calculate power of 101, what should i do then?
For bigger string, Hashcodes are going very big. Should we not use prime number as modulo also?
Thanks Tushar. If I understand this right - Brute-force time complexity is the same as this approach. So this algo excels on looks ups based on hashbased, and when hash calculation maps to collisions then this algo is no good. So do you think brute-force is better given the time complexities are same?
I tried hard but couldn't find your video for Brute Force string matching . Could you please give me the link here.
Have an exam on Sunday. Would really appreciate it.
very helpful ! Thanks
Hey Tushar please can you give me hint how I can make changes in your hash function to allow for one or zero mismatch.
Code seems not working with large input such as ["aabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaa","baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"].
Both of them get the same initial hash, which is weird..
you are not testing at 0th index of string for pattern matching and why didn't you use modulus?
yes , i also commented this
"isnt this approach will create overflow problem while calculating HASH ?? if pattern is more than 63 length.that to in best case . if we choose our prime 2. how can we compute 2^64 . looks like this approach has limitation , we should be using MOD also"
Thank you so much