ADS1: Boyer-Moore basics

[@Dominic_Muller]

This is amazing. These are the most clear and well produced explanations I've seen on KZbin for string searching problems and algorithms. Keep up the awesome work, and thank you for making and uploading these!

[@eugenetswong]

Yeah, so far this has helped the most. It is in easy to understand language.

[@robertpearson8546]

Thank you! I am trying to learn the Boyer-Moore algorithm. But most of the authors are talking about code, not the algorithm. You are the only one that talks about the algorithm. It searches the text from left to right. You are the only one that explains about the alignment. Both the naive and the Boyer-Moore algorithms use the alignment as a relation between the index of the pattern and the index of the text. They both set the alignment to 0 and iterate comparing the pattern with a portion of the text. If there is a match, then the alignment + 1 is the location of the match. If there is no match, then the alignment is increased until it hits its limit (the length of the text - the length of the pattern). The difference between the naive algorithm and the Boyer-Moore algorithm is that for the naive algorithm, the increment is always 1. The Boyer-Moore algorithm uses repeated occurrences of characters and suffixes in the pattern to maximize the increment. The need for the previous occurrences is why the comparison function must go from right to left. (If you want to find the last occurrence of the pattern in the text, you would use the dual of the Boyer-Moore algorithm and compare strings left to right.) The comparison function returns TRUE if there is a match, or the text character that does not match the corresponding pattern character and index in the pattern where the nis-match occurred. (Note that the check for a possible match has already checked the last character so only the length of the pattern - 1 needs to be checked.) Each increment is computed by looking to see if there possible match, do they match, can we increment based on the mismatched character, can we increment based on the suffix found, and can we increment on a suffix of the suffix found. The information for the suffixes can be found in linear time using the Z-Suffix Algorithm (this is the dual of the Z-Algorithm which looks for prefixes, not suffixes.

[@pineappletom102]

I LOVE YOU. My uni teacher explains everything without motive or insight, just giving code examples. You make everything and the reasoning behind it clear

[@pjn2001]

Finally. Someone that can actually explain it clearly. Congrats you even surpassed any chatgpt attempt at explaining this.

[@XavierGeerinck]

Fantastic, 100 times better than my professor!

[@radonsmith4386]

Mine had like 2 slides for this alg. Impossible to comprehend from that if you re starting at zero.

[@dongwang2340]

Cristal clear explanations for Boyer-Moore basics. Very smart and professional.

[@josepharce5218]

Thanks for making this video! Feels so much more simple when you explain it

[@Danny-we4vz]

To anyone who's confused. This guy is good but he didn't explain everything. For Boyer Moore, you preprocess both Good Suffix AND Bad Character Rules. For each mismatch, you take the maximum between these two rules and do the jump.

[@marco.nascimento]

he explains this in the second video

[@minh91a1]

"the mismatch becomes match again" this explains everything ! Really good video, thank you :D !

[@rumshatasneem3120]

Thank you so much for explaining Boyer Moore in a simple yet very efficient manner. Made my concept crystal clear!

[@amylee164]

thank you so much idk why our professor taught us in a way that really confused me you just saved me 40 minutes trying to figure this out

[@TheLevanin]

Hi, I believe there is an error at the slide at 03:40. Isn't the shift is dictated by the rightmost appearance of a character. So the rightmost appearance of C on the right side of the comparison, so it only shifts forward by 1.

[@gentrithalili1483]

Hello, thank you for this video it is so helpfu, but i have one question. Can i solve with "BAD CHARACTER RULE" that second example that you solved with "GOOD SUFFIX RULE" ? Is it wrong or Is it the same solution ?

[@jojojoji24]

but in step 2 of good rule, if u r skipping till "substring" of t matches with substring in P (CTTAC in TACTTAC) then in step 1 T before TAC matches with T of t (T in TAC) then it should skip to T only* (in short should we match whole t in P or a substring of t in P)

[@broski8944]

a million times easier to understand than my prof. thanks

[@fs71gh]

Very clearly explained. Kudos to you. But one question I have. Do we stop when the pattern is found in the text once or we continue searching for more possible matching?

[@colllten]

I know this is 6 years too late, but yes, you stop once the pattern is found in the text and you typically return the index of the first character where the pattern occurs in the text

[@CaptainJerry16]

what if we dont have t. I mean what should i do if first comparison is mismatch? in good suffix rule

[@bioinfo9386]

Great- very clearly explained, thanks a lot!

[@radonsmith4386]

4:40 the way i learned it was the the bad-character heuristic searches for the last occurence of the missmatched character in the pattern (going left to right). So in this case this would be the C to the most right (tg C), wish would result in the pattern being moved to the left. Which is my the Alg also work with the Good-Suffix.

[@usman4life518]

I have a question, what is the different between the boyer-moore and the boyer moore horspool?

[@robertpearson8546]

But what about the STRONG good suffix rule?

[@akrammohammed1167]

Ok. Now this is an amazing explanation!

[@_PranavDesai]

очень хорошо! вы добрий учитель!

[@adarshkanojiya7692]

which is better to use good suffix or bad character rule?

[@jsbisht_]

It would be good if you could tell which way the string matching is happening i.e. from LTR or RTL.

[@ibtsachid9814]

RTL

[@ramla7564]

Thank you! This helped me a lot

[@MrChandufunky]

Thanks man. Wish I had known about this channel before

[@jainamshah3993]

What is the running time for this algorithm?

[@pulkitjatav8550]

Great explanation.

[@ChapaWellappilichapz]

Thanks a lot. Explained really well :)

[@RR-nq1jb]

Thanks for your clear explanation.

[@caine7024]

well explained!

[@ahmadnour3825]

A lot of thanks 🌹

[@salonigandhi8567]

what does it mean to skip 3 alignments?

[@adityabhattar1]

Very helpful. Great Explanation. Thank you

[@sumanththikka1506]

what is diff b&w bad character rule and good suffix rule

[@bilaljan321]

superb

[@Zerreloy]

amazing explanation, you just got yourself another sub

[@esc120]

this explained so clearly! thanks you very much!!

[@Jacked_Nerd]

Thank you

[@robertpearson8546]

The difference between the naïve algorithm and the Boyer-Moore is in how far the pattern is shifted. The naïve algorithm always shifts by 1, ignoring any information gleaned by comparing characters. The Boyer-Moore computes two sets of information. The first is where each pattern character last occurs in the pattern. The second is where each proper suffix of the pattern occurs in the pattern. This information depends only on the pattern, not the sequence being searched. Using this information and information gleaned by comparing characters, the shift is often greater than 1.

[@KulasangarGowrisangar]

Best of all. Thank you!

[@matildaw7287]

Thank you for this.

[@JoseSanchez-vv1zd]

Great video! Thank you sir! :)

[@Epii_]

Thank you!!!

[@gownerjones]

Fun fact: This is the algorithm that makes grep extremely fast.

[@stevenjchang]

link for the videos before and after this one in the series: before: kzbin.info/www/bejne/pqmnlIx-jpaji7c after: kzbin.info/www/bejne/jZuZYWmEZa50qdk

[@shreyashachoudhary480]

Epic!

[@TzuriKatoa]

great stuff! thank you.

[@mawukogermain323]

Clear ! THAHKS !

[@hentetiahmed998]

Thanks a lot :)

[@Cornbreadddd]

I'm very new to this, and these are so immensely helpful. So easy to understand!

[@3salyaa]

can we incorporate the principle of edit distance & approximate matching algorithm into Boyer Moore algorithm? Is it possible to make BM also working as approximate matching algorithm ?

[@prodev7401]

thanks a lot :))))

[@mobeensarwar1609]

tnks brooo

[@universalmighty]

YOU APPROVED MY WORK I LOVE YOU MUAHAHAHAHAHA

[@robertpearson8546]

You omitted the fact that scanning characters right to left is EVIL!. That is why there is the Z-Algorithm for prefixes, but no Z-Algorithm for suffixes. That would be EVIL! And that would make it relatively easy to implement the enhanced bad character rule.

[@alainfreedom3159]

No photo ever of the DNA molecule

[@大盗江南]

Omg... buddy, u r so smart....jesus.....

[@MrBrownpotato]

This explanation of good prefix rule got me a bit confused for a while because later you show an example ( kzbin.info/www/bejne/eYWUnYSEbJiIg9U ) that doesn't follow what was explained here. After watching another video on this topic by Kj Huang (kzbin.info/www/bejne/opyvZ4Whhtujg68) I think you have only explained "case 1" here (entire t occurs again elsewhere in P) and missed "case 2" (prefix of P is matching "suffix of a suffix" of t)

[@overlordskazzel6330]

IAL GODS LEFT ME UNFINISHED...

[@akbaralinabiev]

Is there anyone from 2022 ?

[@jenniferhill8776]

I don't even do this stuff & I'm like, 'Really?!' ' You don't say??...' how dare those Bad Characters go unpunished!

[@PriceActionResearch]

Boyer-Moore starts @ 2:41, he goes on rant for the first two minutes.

[@takeuchi5760]

It's not a rant

[@exp969]

Readings from GFG 😂

[@חןקמחי-ק7מ]

לא מובן החלק השני של הגוד ספיקס הזה

[@2002saketh]

This was a terrible video. This video confused me more than actually teach me. Because of this video, I had to relearn and on top of that I got a C on my pattern matching exam. If I didn't watch this I would've gotten a perfect score.

[@anirudhramesh92]

I agree I think I have seen you around University. Please reach out if you want to study some time 😉

[@SiddhantDubey]

I disagree, I think this video was made very well. - yashas ambati

[@miketruk7639]

People learning to make the tables - dont waste your time he doesnt teach it for whatever fucking reason

[@paidapps733]

"We studied naive exact matching.." try "In ADS1: Naive exact matching, we studied naive exact matching" or "In the previous video. ADS1: Naive exact matching, we.."

[@glimganz]

Thank you