How to match pattern in string - Naive Method and Boyer Moore Method explained | Team MAST

In this video I will explain you the Naive Method and the Boyer Moore method by creating Bad match table.
Note : Naive method is another name for Brute Force method.
So this video covers up both the topics i.e Brute Force and Boyer Moore Method...!

If you have any of these queries -:
string matching naive algorithm
naive method string matching
naive string matching algorithm example
naive string matching algorithm ppt
naive string matching program in c
naive string matching algorithm pdf
naive string matching algorithm complexity
string matching perl
boyer moore algorithm
boyer moore algorithm example
boyer moore string matching algorithm
boyer moore string matching algorithm with example
boyer moore string matching algorithm pdf
boyer moore string matching algorithm ppt
boyer moore pattern matching algorithm example
pattern matching algorithm
boyer moore pattern matching algorithm ppt
explain boyer-moore algorithm
string search algorithm
matching pattern in string naive algorithm
brute force algorithm examples
brute force password cracker
brute force algorithm pdf
brute force algorithm ppt
brute force algorithm for string matching
brute force string search
brute force pattern matching algorithm
brute force algorithm ppt
brute force string matching algorithm in c
brute force pattern matching algorithm example
brute force string matching time complexity

Boom..!! Your search ends here, as this video gonna help you as per you wished.

[OEA]

Thanks, nice explanation. I found that it will miss a match in first example if text would be "welcometeammastto". As you explained "Last letter = length, if not already defined." So maybe you shouldn't override 'T'.
Also, it seems you need to use last unequal character for getting shift and do it relative to it, that introduces necessity of using suffixes table too.. 

[ahmadKha]

sorry but this is wrong .. you missed a lot of things from the original method .. please read about it and practice and then upload the video again so u don't confuse people with this one

[shahpratik]

Incorrect explanation when there is a mismatch. Check for the character in the search string and apply shifts based on that.

[ameyjain]

you say last value is = length if not already defined. T was already defined as 7 then also you changed it to 8, why?

[solavogrey]

The first example is incorrect. When E doesn't match with S, we should shift 6 places (you showed 8) and reach M. M doesn't match with T and hence 3 shifts again and we reach the last T. String matches then.

[vinaygurjar]

Literally The Best Explanation... 🌟 Thank you Team Mast 🌟

[maniratnam]

I think the table values might be wrong. What if the input string is WELCOMETEAMMAST
According to your method it wont find the pattern because you are skipping the 'T' in 8th position after first comparison.

[jennazhang]

Thanks for the lecture! One question at 9:09 of the video. Why when H matches H, T matches T, but O doesn't match S, and you used H value instead of T value?

[harikrushnasolia]

What if Text = xxhhxyz 
Pattern = xhh
It will fail if you put h=2; (Last character = Length of pattern) as you explained

[Nihalnaitik]

Text=This class is data structures
Pattern= data

[srisaiharsha]

In the shifting process when a mismatch is occurred, the value of number of spaces to be shifted is considered from the element corresponding to that of TEXT part. What if the element is not present in BAD MATCH TABLE??

[alex_smallet]

I think this explanation is incomplete. There is only the first part of the algorithm. There should be a second part which is “good suffix” table.

[rheumaticharm]

It is a good technique but when I checked it's implementation it was a bit different. So I got confused. But after a while I found the problem with this technique.
This one cannot match the overlapping strings like:
Text = A Y Z A B A B A B S U
Pat = A B A B
So the matches should be abab at index 3 and 5. But this technique will only give for 5. And this nees few modifications to be able to match both strings.

[ruoxingsun]

try this example
ababbbbaaabbbaaa
bbbb

bad match table{b : 4}

first mismatch is a, it is not in the table, so we move forward 4 characters
ababbbbaaabbbaaa
bbbb



see the issue?

[TheFrozenland]

I dont think it works. If the text = pattern = TEAMMAST, it will slide over it. DOES NOT WORK. PLEASE FIX IT. THANKS

[abdelmalek]

You're wrong when you have shifted the pattern with 8 indexes, it should be 6 indexes

[tushar]

nice one Team MAST..keep going guys...
plzz make a video tutorial on how to find the square root of the number in shortest time possible 

[doml]

This is horsepool not boyer Moore method. Foyer moore method includes a second table

[nikhilnangia]

thanx for it :)
can we have implementation also ?

[TheRaffynator]

This does not work. Try the string "kaccffacc" and the pattern "facc".