Karp-Rabin String Matching Algorithm | Substring Search Pattern

Рет қаралды 30,159

9 ай бұрын

Discover the inner workings of search engines like Google! In this video, we'll explore the Karp-Rabin algorithm, a powerful technique for efficient string searching using hashing.
Take part in the learning in public initiative! Share your learnings on LinkedIn and Twitter with #DSAwithKunal & don't forget to tag us!
👉 Resources
- Join Replit: join.replit.com/kunal-kushwaha
- Lecture code: replit.com/@KunalsReplit/Karp...
- Complete Java DSA playlist: • Java + DSA + Interview...
- Code, Assignments, & Notes: github.com/kunal-kushwaha/DSA...
➡️ Connect with me: kunalkushwaha.com
👨‍💻 Join WeMakeDevs: wemakedevs.org
#dsa #placement

Пікірлер: 46

@KunalKushwaha 10 күн бұрын

DSA + interview preparation playlist: kzfaq.info/sun/PL9gnSGHSqcnr_DxHsP7AW9ftq0AtAyYqJ

@poorpanda9033 9 ай бұрын

If anyone is new to this bootcamp! Let me tell you it's amazing I've completed almost every single videos so far. By the end of the playlist you'll have so much confidence to tackle DSA questions by your own. Just make sure you're following the notes + assignments & Tips that kunal gives !! Some tips that I always remember when i approach a problem (kunal has mentioned it) - Don't memorize, understand the problem / logic - Hard Question is easy for those who have studied, Easy Question is hard for those who haven't - The function will return from where it was called !! ( Recursion )

@_Dream_Dive_ 2 ай бұрын

That last thing is the most important

@KunalKushwaha 9 ай бұрын

👉 Resources - Join Replit: join.replit.com/kunal-kushwaha - Lecture code: replit.com/@KunalsReplit/KarpRabin-Hashmaps

@adolfocarrillo248 7 ай бұрын

Kunal that updateHash method is kind of clever ha!! nice technique!!! Thanks for sharing your knowledge!!!!

@believe_it2380 9 ай бұрын

These videos are so great, i am also done with each and every video, and just looking forward for notification of new Videos, .... It would be very grateful of Mr. Kunal if he could be more frequent in uploading videos, ❤❤ i don't have much patience for your videos

@vaibhavimishra763 9 ай бұрын

Best course i suggested many friends ❤❤❤❤

@sagarsunar6501 3 күн бұрын

Thanks, sir!!

@ShivamKendre-fc3su Ай бұрын

Great video

@jk-sm6qr 4 ай бұрын

Thanks Kunal!!

@sheikhmkrifat7749 9 ай бұрын

Love from Jashore University of science and technology ,Bangladesh Sir❤. I am from non cs, following you to be a selftaught programmer.

@simalinaaz5640 9 ай бұрын

Second video on same day❤

@apjdumer9233 9 ай бұрын

Inspirational ❤❤❤

@easterntoronto 9 ай бұрын

GOAT for a Reason....👍

@ayushprasad8207 9 ай бұрын

Wah ek sath

@lakshitjain6923 9 ай бұрын

Sigma uploaded 2 videos at 3 am

@tusharkumar2290 9 ай бұрын

String has a function called contains( " "). It has Log n complexity :) , Rabin karp can be said as more algorithmic approach whereas contains can be classified as general apporach

@theseriousguy2136 6 ай бұрын

I guess the CalculateHash function will get to the limit of mathematical computations. suppose str.length() is around 1000 It would need to calcu;ate 101^1000 and that is out of bounds of long storage, and I guess pow() too couldn't cacluate it.

@shadowmonarch1432 9 ай бұрын

At 2:20 the example ur explaining is sliding window technique with a TC of O(26*N)(for this problem) = O(N) By the way Big Fan bruh❤️

@shyam4034 9 ай бұрын

Ninnu ekkado chusa bhayya

@bahultyagi 8 ай бұрын

Yes he said its O(n*n) which is wrong

@LowkeyCoder 9 ай бұрын

❤❤❤

@atharvameher5880 8 ай бұрын

Would this work using something non-prime?

@RishiRajxtrim 9 ай бұрын

🙏👍

@elco7956 9 ай бұрын

I don't really understand the updateHash function

@rishu_singh_ 7 ай бұрын

what if we need to count that how many times b string contains a

@sufiserious798 2 ай бұрын

Just use a counter variable, and in the condition where all characters match, increase counter by 1. At the end when the loop ends either return or print the value of counter.

@piyushgupta8763 9 ай бұрын

Cant we just use b.contains(a)?

@shyam4034 9 ай бұрын

That also uses an algorithm similar to this one .

@Bavasharan 7 ай бұрын

Can anyone pls explain why we divide by prime in order to get new hash

@aveshsingh491 6 ай бұрын

since we were multiplying with prime in order to calculate the hash with that character and now since we want to remove that character from our window therefore we need to not just subtract that character but as well divide the new hash with the prime.

@Bavasharan 6 ай бұрын

@@aveshsingh491 tq so much

@ALIHAMZAAKRAM-oe2su 9 ай бұрын

I like to say Rabin-karp is it okay

@KunalKushwaha 9 ай бұрын

yes

@user-tl9cr7ri3p 5 ай бұрын

@NavneetKumar-lg3nv 2 ай бұрын

not able to understand line no 13

@NavneetKumar-lg3nv 2 ай бұрын

got it

@sathishloal5916 6 ай бұрын

Bro actually it takes n-pattern length times iterated and in each iteration it takes two iterations of length of pattern for generating hashcodes and also checking for same characters or not, if hash is matched Finally it also take O(nxm ) time ❤ Tell me if im wrong☺️ But krunal playlist is awesome🧡🧡🧡

@Liku108 9 ай бұрын

Hey kunal can you give a refferal to me

@KunalKushwaha 9 ай бұрын

@Liku108 9 ай бұрын

@@KunalKushwaha ok but please make a video for how to apply for Google

@KaizokuOuNaruto 9 ай бұрын

@@KunalKushwaha40lpa fraud will refer? LOL made fools out of lakhs of people and that devops course has gone extinct just uploads promotion videos of tools these days.. free free ke chakkar me big scam of trust... fraudster kunal

@KaizokuOuNaruto 9 ай бұрын

@@KunalKushwahaYou wont reply to or atleast complete your bootcamp but youll show arrogance for someone asking you a referral politely.. karma hits back fraudster... played games with trust,viral controversies,hype.. and the end result is zero..

@gojosatoru988 9 ай бұрын

@@KaizokuOuNarutowhat karma bro, if you don't like him don't watch his videos. Previously these types of detailed courses were paid, a kind man started it for free while managing his own work, and you're calling him fraud!!!!! Cheap mentality 😞