9.2 Rabin-Karp String Matching Algorithm

[@pushpakwakode5902]

I completed my most of the syllabus from Abdul sir's lectures..just night before exam..no other videos are better than this..

[@Nishu-666]

kitne marks aaye fir bro??

[@LifeIsFreedomNotCage]

@@Nishu-666 tu padhle kal exam hai 9 baje

[@Nishu-666]

@@LifeIsFreedomNotCage mast gaya mera already

[@shantanubapat6937]

Abdul Bari is one of the best teachers of algorithms. You see his video once and you get it no matter how hard the topic is. I wish my teachers in college were like him. If Mr Bari is reading this: Sir Thank you! Can you also make videos on topics like system design?

[@AsifKhan-yn2wp]

Gem of an instructor, if only the algorithms could be explained in a class that way, nobody would be intimated by DSA.

[@Fatality_Retired]

I was confused about this algo for whole day and you just cleared it in just 20 minutes. Thanks a lot Abdul. Subscribed !!!

[@nandkishorenangre8244]

Great content sir ... i have watched video of Geeks4rGeeks , TusharRoy ... but ur content was the one which actually cleared my confusion ... thank you sir

[@livram55]

same here. didnt understand a thing from geek4geeks video.

[@sankethb.k642]

same here left geeks4geeks video at half and came here

[@jayshree7574]

same here

[@codingarena3806]

same bro

[@suryanarayanan5158]

same here

[@xdewtr]

This video clears my confusion by starting simple. I love how you go from naive hash function to show the importance of picking a good hash function to avoid collisions. Great video and subbed.

[@dipchakraborty71]

night before the algorithm exam :D

[@TheKhurram17452]

bro same :P

[@riyanshpal4063]

@Lunatic Fringe back aagyi

[@harshit8638]

@@riyanshpal4063 XD

[@riturajjha]

@@riyanshpal4063 😭

[@ayushsaini9798]

1 hour before exam bro :)

[@vishalc832]

00:04 Rabin-Karp algorithm is a pattern matching algorithm used to find a pattern in a given text. 02:29 Rabin-Karp algorithm uses hash function for pattern matching 05:00 Rabin-Karp algorithm for string matching 07:37 Rabin-Karp algorithm average time complexity 10:04 Avoiding spurious hits with a strong hash function 12:52 Rabin-Karp algorithm allows defining custom hash functions based on text patterns. 15:20 Explaining the process of Rabin-Karp string matching algorithm 17:54 Rabin-Karp algorithm using rolling hash function. 20:04 Introduction to Rabin-Karp string matching algorithm 22:10 Perform mod operation based on data type and maximum size

[@hrishabhsingh5647]

Great explanation sir, you summed up the entire video in just 23 mins and after watching your video, I can understand each and every line of Cormen very easily. ThankYou Sir.

[@cristiangomez7807]

Abdul Bari, this is just a tremendous help. I started deeply understanding after you split the algorithm into several steps discussing the drawbacks. Excellent content. LIKE & SUB

[@Anaximander29A]

Thank you so much! Our professor gave such a random explanation that it simply wasn't understandable, this here on the other hand was perfect!

[@norielgalang1123]

As clear as a bright sunny day! Thank you Sir!

[@EvanMilliken]

Perfectly well explained sir. I had so much trouble in understanding this problem, but the way you taught it, I understood it easily. Thank you sir.

[@VishalKumar-pk9ek]

best explanation ever...👌👌 The one thing which makes you look different from other teachers is that you keep gaps between words perfectly along with perfect body language and hand movement . When I saw 24 minutes videos of other teachers, I feel like yawning😁😁😁😁. But not in your case.

[@vishaldas9312]

I love this algorithm! with average TC being O(m-n+1) as taught by sir, when the two strings are equal, i.e. m = n, the algorithm becomes O(1). In fact the concept that the pattern length reduces the complexity just blows my mind!! They do say it correct, the bigger, the better. Thank you sir

[@bigbrain4071]

Night before DAA exam

[@Ashish-v1d8i]

Spit?

[@pessisum5507]

AAD

[@DivijPatel-tl9ib]

Take pendrive

[@xiaoweidu4667]

only you explained well why the algorithms is engineered that way, thank you!

[@minyoonara]

I was having trouble and anxiety when I saw this in class.. I thought, what is this? Because the teacher didn't give any examples like these. Thank you sir, for explaining these algorithms with simple explanations and visualizing it. It really helped me to understand!

[@gopalmer7116]

Fabulous explanation ....you are a Legend of Algorithm .....this Free resource is very very Valuable for The students who know nothing about an Algorithm

[@joseantoniomartinezquinto5711]

Man really good explanation even for dummies,simple and clear.Nice video. Thanks

[@siddharthupadhyay4246]

Thank you so much sir, you taught way better than anyone could teach with a laptop.

[@dipkumardas3941]

You can't get better explanation of Rabin Karp Algorithm than this one..❤

[@m.aldakheel803]

HE IS THE BEST INSTRUCTOR IN THE WORLD. HE REALLY HELP ME AND MY FRIENDS TO PASS EXAM.

[@therealajmelmuadz]

Amazing video mate. I can't imagine how you managed to fit the main concepts in CRLS's Algorithms textbook for this algorithm in only 23 minutes. Respect for that.

[@ShivShankar-ut4ul]

Absolute gold, never it has happened that I'm not able to understand something.

[@nikkm2000]

One confirmation required sir-> at time 11:01, maximum time in case of spurious hit would be O(n-m+1)m.

[@cy7602]

really cannit stand ppt explanation filled with text and you have saved my life...

[@ieetscode5318]

You can't get better explanation of Rabin Karp Algorithm than this one. Just wow💕💕❤️

[@Mumma90]

Wonderfully clear explanation. Thank you so much! Keep up the good work.

[@nishtha27]

Such patience, thank you, great explanation!

[@hatedbylifeitself6730]

Have a great life, love your profile picture of Touka

[@pranjaltiwari256]

simp

[@Celebs-xyz]

Even my teacher also learning from him😄

[@dhrumilsports3522]

Thanks sir. Teachers like you makes our lifes easy 🙏

[@lorisferragosto6488]

Great content sir...love from Switzerland

[@ASIFAlI-lq4rd]

one of the best and only teacher in thw world.

[@FranciscoJesusNicolasVegaPorta]

best video ever for understanding this. Many thanks!! :)

[@pkyadav6230]

I would like to give you Noble prize for this incredibly helpful playlist sir....in the field of education... 🙏🙏😘🌹

[@RpgSkiTzO]

11:42 pe sir ne aag lga di 💯💯💯💯💯

[@ShubhamKumar-lb4ou]

In the hash function defined by robin... you can just take the hash value of each element and put them in order for example abc (a=1,b=2,c=3) will have code of 123.... you can do the same while matching the hash code from string to save time

[@shaunakjoshi9313]

Bravo sir, this is an epic explanation!

[@pranjaltiwari256]

tu bhi simp

[@JEDhanraj]

Great prof ever seen , hats off you sir . You are doing great work sir . 🙏🙏

[@kaisarshabir2503]

Sir at 21:29 you said that there is still possibility of a spurious hit, how is it possible since we are multiplying it with a power of base equal to the total valid characters. I tried to get the probability of any two different strings having same hash value( char * base ^ pos) it was 0. So will there still be worst case.

[@tsunghan_yu]

I'm confused about it too. It seems to me that if we don't take modulo then there's no collision

[@todxzayn4832]

Tmr is my DAA exam 😂

[@priyaranjankumar1709]

Me also😂

[@priyanshutiwari7075]

Mera bhi kl hain 😂

[@arindamIT]

But Sir, if we perform (a big number)%(2^32)..that will lead to higher chances of spurious hits..because the values of the hash function will be in a small range..say(1 to 10)..

[@kirubelmelak7143]

Thank you for your wonderful explanation. It is so helpful to understand the code and what it's doing!

[@rohitkandula8493]

The Greatest Explanation sir, Thank you i helped me alot to learn DSA.. Only the Computer Science Students Can know the value of this legend's Explanation 🙏🙏🙏🙏

[@desifun9321]

U r great sir, yrr method of teaching this sub is too excellent.you make this sub easier.

[@muhdkhairulamirinum3985]

He is very good at teaching. Thank you for this lesson

[@shikharmalik1622]

421 * we were this close to achieving greatness *

[@eternal2980]

I saw this today on 4/21

[@skaterope]

666 aaaa

[@AnkitJosh]

I'm messaging you this right now at 4:20. Coincidence? I think not 😂

[@Agent_Ax]

@@AnkitJosh Ah You Should Have Focused Lol

[@tanishsharma5852]

@@AnkitJosh Damn! I'm reading it at 4:20 lol.

[@simonchan858]

You are so smart and presents all things clearlly

[@zxborg9681]

I've watched many of your videos. You always explain the concepts very well. I would like to make two small suggestions, though. The elements of a string (a,b,c) are LETTERS, not alphabets. The alphabet is the set from which the letters are taken. Also, when multiplying two numbers, you multiply BY a number, not "into" a number. "into" is usually used to describe division, as in "5 into 100 is 20". Whereas you multiply 5 by 20 to get 100. Anyways, thanks for making these videos, they're great!

[@saurabhsoni738]

Very good explanation , it cleared all doubts

[@mohamadhosseinfakharan]

Hi. Thank you so much. You explained it very well from the beginning. I understand it completely. Thanks a lot.

[@ashishsinha8893]

I think sir u r working in algorithm its great to se u in advance algorithm lecture

[@SarbojitGanguly]

Fantastic explanation sir. Helped me immensely.

[@thefuntech2810]

Sir It's an excellent video i am a big fan of your knowledge please share this knowledge with us

[@khushboosharma5417]

You always make every problem simple and interesting!!!

[@Jaffer420]

Wow what an explanation . I guess i just found the treasure .

[@sujoyseal195]

In C++, we cannot store values greater than 10^18 . So, the second has function worn't work for cases where length of pattern > 18 . Even if we use modulo , there are still chances of collission since even if p!=q , mod(p) may equal mod(q) . So, we need a different hash function for practical purposes.

[@frankop3857]

Thank you. Especially the method with the better/accurate hash.

[@abdulrafay2420]

Behtreen hogaya bari bhai❤❤

[@DJD1001]

Tomorrow is my DAA exam at 9:30 sharp and I am watching this 😂

[@Rohitrootn]

Was asked in oracle interview

[@anujapatil1485]

Hello Sir, this was a great video about Rabin Karp algorithm. I have a question about its time complexity. Could you please explain why it is O(n - m +1) ? Should not it be O(n+m) because in the best case if we find the pattern which is matching in the text, then time to check that pattern is O(m) OR in the case where the pattern does not exist, then would not the time complexity be O(n) ?

[@sparshnagpal1509]

If a text has 11(n) chars, a pattern has 3(m), till 8th comparison max there'll be no results, 9th there will be since[9-10-11], so 11(n)-3(m) +1(the one where you find it, 9th in this case).

[@iubob98]

@@sparshnagpal1509 so the +1 is not because its a 0-based indexing?

[@vijayasonkusare5130]

@@iubob98 no

[@cemtunaboylu8421]

@@sparshnagpal1509 You still have to hash which is O(m) thus in total O(n).

[@manaskarlekar5932]

We have so much confidence in you that, after coming to the video page, we first like your video and then watch the full video

[@koyavasudhalakshmi2073]

Very helpful sir, very clearly understood sir🙏🙏🙏

[@reethik2759]

🐐 Greatest of All Time

[@himanichoudhary652]

Thank you very much Sir. Please keep posting such videos. They are very very helpful. Kindly do a course on gate questions as well.

[@dhrroovv]

best explanation of rabin karp algorithm!

[@mateuszjanik9646]

This was very clear and understandable for me :)

[@nnamdiwilliams1498]

This was very helpful. Thank you Abdul.

[@youtube.comvideo2490]

sir please try to make one video lecture for string matching with finite automata

[@janvisingla3746]

Great video Sir!!But Please provide implementation of the algorithm at the end of the video

[@nikhilgoyal8340]

Also one more thing, we can still have spurious hits, although chances are very less. For example hash code for 'dab' = 421 and hash code for 'dak' also = 421.

[@alfonsobarona]

You're missing an important aspect about the selection of the hashing function. The reason why '10' is selected as the base is because there are 10 characters ('a' to 'j') in the character set of the text; 'k' in pattern 'dak' would mean that there are more than 10 characters in the set, so the hashing function would change. That way, you wouldn't get spurious hits

[@nikhilgoyal8340]

Jerry Barona thanks for the clarification. Totally overlooked this thing.

[@qayyumblazer]

good explaination also you look like an indian pablo escobar without moustache

[@namandeepsinghhora8956]

your teaching skills is excellent this video help me alot..

[@sydneystriker5355]

Once you have done mod how will perform rolling hash? Ans: just do as it is. The value might become negative while rolling but mod will again make it positive

[@soicooc3500]

have watched video of Geeks4rGeeks but i don't understand until i seen your video it break all my confusion

[@Anubis10110]

Great gradual explanation, thank you so much sir.

[@student0237]

Watching one hour before exam 🙂🙂

[@prudhvic4]

When we do mod, does it not alter the hash value such that we cannot further perfrom a rolling hash calculation?

[@ianthepro]

Thanks so much, u broke it down and built it up gradually! i understand now

[@reyazahmed9320]

Great work. Made the algo crystal clear

[@exoticme4760]

you the best

[@javateam9818]

Great teacher and great teaching method

[@synthesis9455]

Thank you sir for the explanation!

[@jatinkumar4410]

Very clear and to the point explanation. Thank you sir.

[@jaikumargupta1368]

11:27 lecture starts

[@MrSaiyah007]

In the example of the hash function used on the video, how are we going to handle overflow for very large strings, since we keep summing the length*pow(ascii, m-x) ?

[@ketanahuja8939]

use mod

[@ViswanathanMurugesh]

Great Lecturer. Super clear and keep it up.

[@sarthakbhatia7888]

Why was the average time theta(n-m+1)? 7:49

[@ksenijasokic3464]

When you do n-m, you are left with end of a string length of m, and that is just one more check, so you have n-m+1

[@sarthakbhatia7888]

Ok got it.We are going from 0 to n-m so time is n-m+1

[@jun_1248]

He was my teacher at MJCET. Good old days.

[@nickwalton1109]

Excellent style of instruction

[@dominicrider5050]

Sir it would be really helpful if u included the actual algorithm too

[@pulkitjain9191]

Great explanation, it makes easy to understand logic, thank you sir

[@aditigupta2684]

Very wonderful explaination sir 🤗

[@dr.joychristya8937]

you are simply amazing sir... thank you so much.....

[@md.sabbirahmed9029]

I am fan of your teaching.

[@TheEnde124]

Maybe you should explain that you should use prime numbers instead of 10, and use modulo with a prime number again if needed, to further help avoid conflicts.

[@sarfarazalam6077]

Great explanation sir!!! Big fan of yours.

[@5hadowAJ]

Is the algorithm more efficient than using (python) >>> if (pattern in text) return 1 ?