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

@GeeksforGeeksVideos

7 жыл бұрын

Thanks Connor for the appreciation!

@satyam1945

4 жыл бұрын

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

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

@muditkhanna8164

11 ай бұрын

you probably watch too much tv

@user-fs3qr5yg7e

10 ай бұрын

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

@rubyshorts281

2 ай бұрын

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

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

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

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

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

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.

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

@xSolBadguy

3 жыл бұрын

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

3 жыл бұрын

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

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

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

4 жыл бұрын

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

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.

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

Amazing all your tuts!

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

Does anybody know what exactly 'h' is?

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

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

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

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

how is that formula derived

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

@ytg6663

3 жыл бұрын

Yes

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

3 жыл бұрын

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

3 жыл бұрын

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

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

But why 256 is multiplied in calculating the hash value?

@danishrockz1

2 жыл бұрын

no of all special char + letters is 256

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

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

@-Good4Y0u

6 жыл бұрын

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

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

@sofialpaca2563

4 жыл бұрын

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

@satishtyagi4711

4 жыл бұрын

@@sofialpaca2563 okk.

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

can you give the video more volume?

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

@RasikBihariTiwari

6 жыл бұрын

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

5 жыл бұрын

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

Fantastic explanation

Similar to sliding window technique🙄

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.

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

@Manu-wb2uv

4 жыл бұрын

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

@jaatharsh

3 жыл бұрын

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

3 жыл бұрын

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

3 жыл бұрын

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

3 жыл бұрын

@@jaatharsh okay thank you!

does it matter what prime number do i use?

@snandhininvrzmsywqh2687

4 жыл бұрын

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

@stv3qbhxjnmmqbw835

4 жыл бұрын

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

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

360p only ? 😭

Don't dislike free education.

Why not comparing ASCII

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

@RasikBihariTiwari

6 жыл бұрын

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.

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

class Solution { public int strStr(String source, String target) { int M = source.length(); int N = target.length(); if (M 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 preCompute = (preCompute * d) % q; // (a%n * b%n)%n } for (int j = 0; 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 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; } }

Is i'm too late ...

Audio quality is very poor 🤦

Illuminati???

@GeeksforGeeksVideos

7 жыл бұрын

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

@tomellsworth7735

7 жыл бұрын

HAHAH !

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.

Not well explained 🙄

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

@GeeksforGeeksVideos

7 жыл бұрын

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

@tomellsworth7735

7 жыл бұрын

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

not explaining properly not making any sense

Worst explanation

Nothing is clearly explained, dissapointing

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

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