Rabin-Karp Algorithm | Searching for Patterns | GeeksforGeeks

[@academicconnorshorten6171]

Incredible Website, improving at a very impressive pace, please keep it up!

[@GeeksforGeeksVideos]

Thanks Connor for the appreciation!

[@satyam1945]

C Shorten try nptel its old but gold ,use 1.5x speed.

[@user-fs3qr5yg7e]

simple and straightforward - got it instantly. it beats the MIT longhaired genius guy with his confusing scribble on the table by miles.

[@muditkhanna8164]

you probably watch too much tv

[@user-fs3qr5yg7e]

i was referring to an actual video on here on yt, not to a clichee@@muditkhanna8164

[@rubyshorts281]

how is pow(d, M-1) % q is computed using this for (i = 0; i < M - 1; i++) h = (h * d) % q; ??

[@nixuser1980]

Could you please upload a 1080p version of this video since: 1) the text is hard to read; and 2) this video is obviously of high value to us CS students.

[@follow6460]

Thanks, of course my teacher explained it like it was the entire theory of relativity.

[@nikhilarora6043]

would be great if you can spend some time on explaining the calculation of complexity.

[@luischinchilla-garcia5640]

Awesome explanation, but absolutely horrendous use of variables. a,b,c,d,h.... are all bad and confusing choices that make the code almost unreadable. Use more descriptive names.

[@walkthroughonthego2476]

not sure why the quality of the video has been compromised. it would be great if you could make it better.

[@sanyuktakate4099]

why is it necessary to convert the negative hash function of text to positive? Why cannot we work with negative hash function?

[@hangchen6131]

Thanks for the video, it is great, but I have a question. Why the best case is O(N+M)? Since first we have to calculate the hash value of pattern which is O(1), fine we can get rid of that, but then we have to make (N-M+1) iterations, which should roughly equal to O(N-M)? And then assume we can find the pattern and compare character by character, which needs O(M), then, isn’t the complexity O(N)? Where does M come from? Thanks!

[@moonybloke]

It is too late probably, but what I see, that the FIRST hash value is calculated with O(M) complexity. Only the following one will have O(1) complexity. That's where we get it

[@coltennabers634]

Look at the first for loop that sets initial hash

[@xSolBadguy]

"Next we do d ^ (m - 1)" (PASTES SOMETHING COMPLETELY DIFFERENT)

[@xSolBadguy]

God, this is done so badly. For those wondering, you get h by doing h = d^(m-1)%q. The %q is very important, but I guess he just didn't feel like saying it audibly :)))

[@N-e0N]

@@xSolBadguy But why do we even use h? Like what's the purpose of multiplying text[i] with h?

[@francoocampo5286]

can you give the video more volume?

[@sunnykhandare6051]

Can any body explain why 'h' was calculated , why 'h' was multipled in the eqn " (256*(previous_hash - h*first_char) + next_char ) % 11 " .

[@N-e0N]

Hi, its been a year since you asked this, so did you ever manage to find out the reason for that? Because I'm confused about it too..

[@juanbomfim22]

@@N-e0N To find the hash for the pattern, it's needed to convert it to a number and, to reach it, the algorithm needs to do some calculations with its letters to return a corresponding value. The idea is basically to use the base conversion logic that allows you to write any number and find a corresponding single value. For example: the number 101 (base 2) is expressed as 1.2² + 0.2¹ + 1 = 5 in base 10, which cannot be obtained by any other combination, one of the reasons why it was chosen. However, in this situation, we have letters, not numbers. Well, one solution is to convert them using some function that maps each letter to a number. Fortunately, when you do t [i] (which is a letter) times a number, C converts t [i] into a corresponding number following the ASCII table. In this case, we write in the base "d" the pattern "GEEK" So, from "GEEK", I get: t = ord (G) .d³ + ord (E) .d² + ord (E) .d¹ + ord (K) And from "EEKS": t '= ord (E) .d³ + ord (E) .d² + ord (K) .d¹ + ord (S) To save calculation time, if you look carefully, you can rewrite t 'in terms of t: t'= d (ord (E) .d² + ord (E) .d¹ + ord (K)) + ord (S) t '= (d. (t - ord (G). * d³ *) + ord (S)) (Some% q hashes are made throughout the calculations and have been omitted) Now it shows where h = d³ comes from

[@vinaysridhar2588]

In the GEEKSFORGEEKS example the hash value of EEKS was both a1 and a8😅

[@ytg6663]

360p only ? 😭

[@afzalsiddique7165]

Does anybody know what exactly 'h' is?

[@nandkishorenangre8244]

Looks like u tried ur best but i am still having some confusion in the last if statement :(

[@ytg6663]

Yes

[@coolstuff9837]

if we are not using 'h' in the code then also answer is coming right . So I want to ask whether it is ok if we don't use 'h' ?

[@SearchingPeaceInside]

But why 256 is multiplied in calculating the hash value?

[@danishrockz1]

no of all special char + letters is 256

[@-Good4Y0u]

What happens if you have wildcards... Smaller search window ?

[@satishtyagi4711]

What is the need of checking each term if hash value matches? I mean same string produce same hash value.

[@sofialpaca2563]

Because the hashing function isn't bijective, you're supposed to recheck the pattern for each char if the hashes match.

[@satishtyagi4711]

@@sofialpaca2563 okk.

[@ayushjain7714]

what is exactly 'h' here? h=d^(m-1)

[@lingasodanapalli615]

The voice is very low. Can't hear at all

[@joydevdutta117]

This is the best video on KZbin about Rabin-karp Algorithm... Thanks geeksforgeeks ❣️

[@mansijangid8017]

can you please explain why we calculated the value of h ??

[@shalinisivakumar6881]

Similar to sliding window technique🙄

[@rheumaticharm9551]

Why do we need to mod with a prime number only? Can't we do it with some other number?

[@ashishmishra672]

It is a little confusing. A little complex rather but I understood the logic. Thanx.

[@sktousifbakkar7470]

"number of character in alphabets." what does this means

[@RasikBihariTiwari]

Number of characters in alphabets is 26 only i.e. A-Z. But in strings that you process, you can have alphabets (upper case as well as lower case), numbers 0-9, and special characters as well e.g. '+', '=', underscore etc. So this entire printable set of characters are collectively called extended ASCII character set in which each character maps to an integral value from 0 to 255. You can check all the characters of extended ASCII characters here - www.asciitable.com/. This is the reason why the presenter has taken the value of d ("number of character in alphabets.") as 256.

[@reyou7]

You are right, Regular ASCII contains 128 characters, 256 one called Extended ASCII. IMO, it should be mentioned this way, not alphabet.

[@kedarnadkarny4718]

Awesome tutorial. PS- What's with the high voice modulation at the end of each sentence?

[@RepublicofKor]

You mean the number of ASCII characters, not alphabet here.

[@chintusharma1]

Why not comparing ASCII

[@ammulu1021]

I can't understand how pat(I) and txt ( I) values come

[@vikasjilla4522]

how is that formula derived

[@1998charan]

Can anyone tell me what is the purpose of h? I don't understand.

[@Manu-wb2uv]

That's what I'm looking to find out as well

[@jaatharsh]

hash( txt[s+1 .. s+m] ) = ( d ( hash( txt[s .. s+m-1]) - txt[s]*h ) + txt[s + m] ) mod q 'h' is used to remove the leading character/digit from the old hash values we are deducting " txt[s]*h ", if you see in the formula, here t[s] = leading/first character used to create the current hash value. Let me support this with an Ex:- Let current hash value is 543 if d = 10, m = 3, t[s] = 5 H = d^(m-1) = 10 to power 2 = 100 so what we want is we get rid of 5 so we achieve this by 543 - 5 * 100 gives us 43 Now we multiple this by d as shown in the formula to get 43*d = 43*10 = 430 and at last add new digit lets say which is 9, so 430+9 = 439 voila u got ur new hash. PS: in the above example, I am using prime no i.e, q = '101'

[@harish1937]

@@jaatharsh thank you for the explanation, I was trying hard to understand that part. And I still don't understand the use of "q" here. Can you please explain?. Thank you!.

[@jaatharsh]

@@harish1937 q keep the largest hash we get in check, calculating hash without it for longer patterns would go beyond max value. Ideally, we can set q as some large prime number.

[@harish1937]

@@jaatharsh okay thank you!

[@neerajjoshi9493]

I understood for best and worst case but how average time is O(n+m)? please explain

[@-Good4Y0u]

neeraj M is the length of the patten, when you find a match you have to check with this. And N is the text , because we are still moving 1 by 1 you are going over the length of the text . What makes this better is the hash takes out a 1:1 comparison for the pattern to text Everytime and you only have to do it to essentially double check at the end when/if you get a hash match

[@yuvrajmann2428]

Don't dislike free education.

[@ElhamKohestani]

What is Sky value? It should be ASCII value I belive but anyway it was a nice explanation. There are a lot of questions about 'h' and would have been nice if you had the explanation for the existence of 'h' as well.

[@paungabriel9360]

does it matter what prime number do i use?

[@snandhininvrzmsywqh2687]

Yes ! Generally either 7,11,13.. It shouldnt be too small like 3.. The higher the prime value, more complex it gets

[@stv3qbhxjnmmqbw835]

@@snandhininvrzmsywqh2687 It should be large ig, because otherwise collision of hash values for non matching strings would occur frequently and your program ends up comparing more strings hence reducing the efficiency. Also I don't get your point of how higher prime makes things complex?

[@atharvavaidya6230]

Fantastic explanation

[@Youngermaster]

Amazing all your tuts!

[@gokulnath589]

Audio quality is very poor 🤦

[@souravjoshi2293]

kuch to background Diya karo. Intuition kya hai, thought process kya hai, bas direct bata diya hash use Karna hai, code walk through kara Diya. waste of time.

[@pk3059]

class Solution { public int strStr(String source, String target) { int M = source.length(); int N = target.length(); if (M < N) return -1; long preCompute = 1; // to compute the mod of remove digits, base^(N-1) % q long hSource = 0; long hTarget = 0; long d = 31; // base long q = 1000000000000000003L; // hash table size for (int i = 0; i < N - 1; i++) { preCompute = (preCompute * d) % q; // (a%n * b%n)%n } for (int j = 0; j < N; j++) { hSource = (hSource * d + source.charAt(j)) % q; hTarget = (hTarget * d + target.charAt(j)) % q; } if (hSource == hTarget) return 0; for (int j = 1; j < M - N + 1; j++) { hSource = (hSource - source.charAt(j - 1) * preCompute) % q; // remove first digit hSource = (hSource * d + source.charAt(j + N - 1)) % q; // add new last digit if (hSource == hTarget) { if (source.substring(j, j + N).equals(target)) return j; } } return -1; } }

[@madhus1025]

@GeeksforGeeks what if my length of both string is greater than 1500 ?

[@RasikBihariTiwari]

I doubt it really matters as long as m (length of pattern) is less than or equal to n (length of text). Algorithm steps have been explained in terms of n which can be 10, 100, 1500 or 1600.

[@nandakumart2331]

Is i'm too late ...

[@gertvogel7765]

i dont understand your words with this accent.....deleeting character????

[@GeeksforGeeksVideos]

There are English subtitles available as well for this video. :)

[@tomellsworth7735]

nice of you adding subtitles. I didn't get that either.. deleting character. Whaat. Cool vid man, thanks

[@saurabhsoni738]

Not well explained 🙄

[@The_Soul2]

not explaining properly not making any sense

[@rushidesai2836]

Illuminati???

[@GeeksforGeeksVideos]

Illuminati is one of our contributors, who wishes to stay anonymous.

[@tomellsworth7735]

HAHAH !

[@danishraza3061]

Worst explanation

[@Roastmaster704]

Nothing is clearly explained, dissapointing

[@persiashahdi5215]

Maybe find someone who can properly pronounce English words if you're uploading a video tutorial representing GeeksforGeeks officially?

[@berni2905]

why do Indians always say _v_ instead of _w?_ I don't get it