Wow. You literally blew my mind. How you describe in such depth and detail astonishes me. I literally understand this algorithm so so well now, I know it better than I know myself. I feel invincible with this knowledge, like I could conquer ISIS just through string matching alone. Thank you, Mike Slade, you have truly changed my life.
After watching this video 3 years ago, my chakras immediately aligned and I knew why the Almighty One placed me upon this Earth. I set about my mission - to destroy ISIS using string matching alone. 3 years have passed, although it seems like an eternity. Guided by Mike's passionate voice and in-depth knowledge of the Boyer Moore Horspool Algorithm, I walked to the hostile Middle East and began my task of removing ISIS from this floating Space Rock. I have listened to nothing but this TH-cam video on repeat to drive my goals, and I have been somewhat successful. ISIS have certainly weakened during my time here. I preached to the locals, pleading them to place their trust in hard toothbrushes. At first they were resistant, but I have managed to gather a large community of followers. With this trusty video by my side, I have been able to accomplish the impossible. Mike, you are a wizard.
Your video explains the concept of boyer morre using bad match table is the only video on using with correct explanation using this method thanks from bottom of my ❤️
Thank you for this excellent example, it was extremely easy to understand and I feel like I can write my own implementation after just one watch. Can you please write all my course textbooks? Lol
Please correct me if I am wrong, but at 4:58 it is mentioned that we shift by 5 because of H wrong? Shouldn't we shift by 5 because the letter "S" that is not in our Bad-Table-List and thereby shift with the "*" value that tells us to shift by 5? It comes to the same amount in this example of shifting but if H had another value than 5 it would have been wrong. Because in the other cases we also shifted by the value of the letter above that didn't match our pattern at that point (H not T -> shift by T; H not O -> shift by O; and so on). As said before, if I am mistaken or didn't understand it right please correct me on this.
You always look up the first character you attempted to match for a given alignment. Not the character that caused the mismatch. Therefore we lookup H at 4:58. This is consistent with the rest of the alignments.
Mike is at the height of his powers, developing algorithms that go unseen to the naked eye, yet influence us all cerebrally, sub-consciously. Little is known about Mike Slade, some say he has no true bodily form and is a mere cloud of knowledge surrounding Horspool Algorithms, others say he is a simple fellow from the Shire, going about his merry way in this life, educating others and shunning fame. Lest, should we investigate further? Or be captured by thine curiosity? Tantalized by the unknown? I know which path I shall walk fellow TH-camr, join me in bathing in the unknown.
I just dont understand 1 step, why when you had your first mismatch you looked to the text and moved 1, but when you hit S, you looked for H because it was the length, or something like that? Can someone explain to me when i look to the text, and when i look to the table
What if the pattern was aaaa, and the generated table would be just one shift for a. Then if I wanted to compare it to the text axaaaabb, then the mismatch for x in the text would make the pattern shift 4 instead of 2(and we would miss the match)?
Hi, I am sorry I am digging up the subject, but one little think about the case that can have exactly n mismatches even m is greater than 0. This is a case when the implementations meets the users :). The case is simply when the pattern does not exists in entire source string. So practically it will be then Success - Mismatch(n-m) times - Success at (n-m) +1 complexity: (((n-m) +1) x m) Fail - Mismatch(n) times - Fail at (n) complexity: (n) Such fails are also costs for the alghoritm if it is exposed to user. Somtimes it is useful to know them, especially when you exposes a public service From the hacking perspective if only length of the source string is known as "n" and the input pattern length is "m" then finding pattern complexity would be (S x n) + (((n-m) +1) x m) where S will be a permutation of length of possible single characters with all possible lengths of patterns them-self. ;)
Sorry, I have a question. At the second alligment, the S doesn't match the O. So I have to look in the table for S, there isn't, so shift by 5. In the video you look for H. Same result, but I think the process is wrong. Isn't it?
No. When there is a mismatch at a given alignment, the rightmost character of the current alignment is looked up, not the character where the mismatch occurred. Hence, the 'h' was looked up rather than the 's' ;)
The adjustment after mismatching S at 5:04 seems odd. Let's say the pattern is THOTH instead of TOOTH, this does not affect the adjustment value for S, since S is still not in the pattern. But shifting by 5 in case of THOTH will potentially miss a match, e.g. the text could be TRUSTHOTH..., am I missing something?
Checked other video, it seems that the index character used to look up the skip table should be the right most character in the text at the current alignment, which may or may not be the right most character in the pattern. Using the mismatched character to look up skip table will not handle repeating pattern like THOTH correctly.
What if the pattern is TOOTHT? Last character is the same as first, so the value for T becomes 0 or 6? Which means either no shift or 6 shifts. In each case, the algorithm fails, I think.
You have to calculate length - index - 1 for each character, except for the last one in the pattern. So the value for T would be 5 for the fisrt T, then overwritten to 2 for the second T and kept 2 for the last T, because this is the last character of the pattern. So the value for T would be 2.
@Ahmed Hammami Letter H is the last letter in the pattern, and thus it gets the value of the length of the pattern, if not defined otherwise. For example, in the pattern: AIRPLANE, the last letter E, gets the value of 8.
Thank you for the video. Now everything is clear. However, I still have a question. Let's say that we have: truoth... (string ) toath (pattern) TABLE: h = 5 t = 1 a = 2 o = 3 * = 5 The first shift is obviously equal to 1. But what is the second, 5 (assignet to 'h') or 3 (assignet to 'o')?
First of all, thanx for the video ! But I have a question too. In your case when S doesn't match O , the rightmost character is looked up, right? You have mentioned that in a reply. But if given text is 'ATCGTGACTGTAATGATGAGAGGTAATGTCG' and the pattern is 'GAGAG', your method cannot find the pattern matching because it skips the pattern in the text. How do you explain that?
I have tried the algorithm on the problem you gave here, and it does find the pattern when I try it. What does your table look like? I have G = 2, A = 1 and * = 5
This comment is pretty old but maybe others experience such an issue with their code. Things you should check to ensure your algorithm works right: 1) Did you set up the correct shift table? Many people do mistakes at the point where you have patterns like: HAHAH -> the last character is H but you cannot simply set it to 0 using the formula he mentioned in the video! Watch it again and listen careful to 4:02 ! Do not overwrite the value of the last character if it already exists in your table! 2) Do you really shift correctly? Often people just do: GACTG GAGAG -> well, T is not equal to A ... lets just search for T inside the table !! NOO !!! DONT DO THIS!! xD He also told you how to do it right (listen to 4:50), search for the first character that matched. This means at this point we have to search for G inside our table. >>>>>>>>> I think "2)" will solve your problem. G matched first -> G in table -> shift = 2 Step 3: CTGTAATGATGAGAGGTAATGTCG GAGAG -->> G != A -> A in table -> shift = 1 Step 4: TGTAATGATGAGAGGTAATGTCG GAGAG -->> G != A -> A in table -> shift = 1 Step 5: GTAATGATGAGAGGTAATGTCG GAGAG -->> T != G -> T not in table -> shift = 5 Step 6: GATGAGAGGTAATGTCG GAGAG --> A != G -> A in table -> shift = 1 Step 7: ATGAGAGGTAATGTCG GAGAG -> G = G -> A = A -> G = G -> T != A -->> G matched first -> G in table -> shift = 2 Step 8: GAGAGGTAATGTCG GAGAG -> G = G -> A = A -> G = G -> A = A -> G = G -->> EVERYTING MATCHES -> PATTERN FOUND! -> shift = 5 Step 9: GTAATGTCG GAGAG -->> T != G -> T not in table -> shift = 5 Step 10: GTCG GAGAG -->> Pattern Doesnt fit in source anymore -> finish CONCLUSION: pattern found (see step 8) Hope I could help someone with that :)
Thank you so much, there seems to be two different levels of Boyer-Moore algorithms. The basic one as this video taught, and an advanced one with good suffix and bad character.
Brilliant explanation! Could you help me with the following question: truoth... (string ) toath (pattern) TABLE: h = 5 t = 1 a = 2 o = 3 * = 5 The first shift is equal to 1. But what is the second, 5 (assignet to 'h') or 3 (assignet to 'o')?
boyer moore and horspool algorithms are different the video you explained is horspool's algorithm boyer moore is littler different please change the title to "horspool algorithm"
For all those out there watching this and actually can think for yourself instead of mindlessly believing in everything. This video is wrong. It would not work if the combination was for example THOTH. Main point is, the increment should be done from the current position in the text, not the end of the chunk. I.e. the +5 should be counted from S at 4:55, not from H, therefore shifting to HARDT instead of ARDTO. OP should take down this video given how much misinformation it is propagating.
By 'if the combination was for example THOTH' do you mean if the pattern was THOTH instead of TOOTH? In that case you are correct it will not work as you need to construct a DIFFERENT bad match table. Shifting to HARDT instead of ARDTO at 4:55 is pointless for the 'TOOTH' pattern. Why bother comparing the leftmost H in HARDT with the leftmost T in TOOTH?
@@mikeslade8772 Thanks for responding! Let's walk through this algorithm together. If you used THOTH and the text was TRUSTHOTHTOOTHBRUSHES, the table will be the same because we always take the rightmost value of the alphabet in the pattern. So [T:1, O:2, H:5, ' ':5]. If we apply your way, we will get to the step where we are comparing T *RUSTH* OTHTOOTHBRUSHES to THOTH in the pattern. If we shift 5 space like what you did, we immedidately jump to comparing TRUSTH *OTHTO* OTHBRUSHES to THOTH. Your algorithm fails to find the pattern. The correct algorithm is to apply +5 to the current mismatch. So since the mismatch is at S, we should instead shift to TRUS *THOTH* TOOTHBRUSHES and you get the correct result. The whole point of the horspool algorithm is to match up the current misaligned character in the text and pattern, your proposed version simply doesn't do that. To give another example, let T be TRUSTHARDTOOTHBRUSHES and P be UBEST, initial comparison is *TRUST* HARDTOOTHBRUSHES and UBEST. What we want is to match up the U. By your method we are going to count 4 from T to get the new endpoint, which will give TRUS *THARD* TOOTHBRUSHES and it does not align them at all! Instead the count should the current mismatch, which is U, so we get TR *USTHA* RDTOOTHBRUSHES. Hope this helps you see your error.
@@mikeslade8772 Also would like to point out that it does not make sense to say doing xxx is pointless for a specific pattern. The whole point of an algorithm is to propose a general solution for a class of problems. Just because it is not useful in this pattern doesn't mean it shouldn't be done.
@@Kuro-uc4jp you have constructed the bad match table incorrectly. H is not 5. The rightmost character in the pattern is the length UNLESS already defined (as shown on the slides). H should therefore be 3 for the pattern THOTH. ( length - index - 1 = 5 - 1 - 1 = 3).
This video was too long. Halfway through it, I got hungry so I left it playing and went to the kitchen to fix my self a sandwich. But then I found out that I'm out of mayonnaise so I went to a store. There, I saw the most beautiful woman I have ever seen in my whole life. But I'm really a shy person so I took up a three-year personality development course so I can introduce my self. She was very friendly and all, but unfortunately, she has a boyfriend. So I said, all good, I'm a mature person. I want the best for her and I harbor no illusion that I am the best person for her and she seems happy with her boyfriend, so I did not bother her anymore. But we kept in touch and we became friends and I got over my crush on her. Then she broke up with her boyfriend, we drank some alcohol because of it, I told her she'll be fine and I wished her well. I still think she's the most beautiful woman in the world, but like I said, I am over my crush on her. It was like five years already when I first saw her. Besides, I am quiet happy with the friendship I developed with her. It was more important than a crush. So we kept hanging out, drinking, having coffee, and all. I had a girlfriend, she started dating other guys. My girlfriend wants to live some other life without me in it, so I said, okay, I want the best for you and I want you to pursue your happiness. My lady friend and I drank alcohol about it, and she gave me the same advice I gave her when she was in that position and I became okay with the breakup immediately. But we were really drunk, so she spent the night in my apartment. I only have one bed, so you know what that means: She took the bed and I slept on the couch. But on the couch, I really can't sleep. Something was bothering me. So I tossed and turned for about three hours, then I finally can't take it anymore, I stood up and went straight to my room where she's sleeping. I approached the bed, gently sat on it and I reached for her shoulder to pull her closer to me. She stirred and woke up. She asked what's up. I told her, you know, the first time I saw you, I was watching a video and left it playing to get my self a sandwich then went to the store to get some mayo then I got distracted by life that I forgot to finish the video. She said, you know what, I've been wondering about a weird noise in your night drawer. So we opened that drawer, and lo and behold, there's my phone and this video still has two minutes of play time on it.
Bro, my professor explained this in the worst way possible, but your explanation is so awesome and to the point. Not everyone is a great teacher.
Wow. You literally blew my mind. How you describe in such depth and detail astonishes me. I literally understand this algorithm so so well now, I know it better than I know myself. I feel invincible with this knowledge, like I could conquer ISIS just through string matching alone. Thank you, Mike Slade, you have truly changed my life.
M Lee Have you developed String Matching superpowers? Can you match strings faster than a speeding bullet now?
You are now made up of strings, and you can efficiently search within yourself with this great algorithm.
If he "literally" blown your mind then you'd be dead :p
bit dramatic
the glazing is crazy
After watching this video 3 years ago, my chakras immediately aligned and I knew why the Almighty One placed me upon this Earth. I set about my mission - to destroy ISIS using string matching alone. 3 years have passed, although it seems like an eternity. Guided by Mike's passionate voice and in-depth knowledge of the Boyer Moore Horspool Algorithm, I walked to the hostile Middle East and began my task of removing ISIS from this floating Space Rock. I have listened to nothing but this TH-cam video on repeat to drive my goals, and I have been somewhat successful. ISIS have certainly weakened during my time here. I preached to the locals, pleading them to place their trust in hard toothbrushes. At first they were resistant, but I have managed to gather a large community of followers. With this trusty video by my side, I have been able to accomplish the impossible. Mike, you are a wizard.
It did not understand ur reference of hard toothbrushes. Any updates after 3 months?
Of course you don’t understand the reference. You know nothing, Jon Snow
damn
Your video explains the concept of boyer morre using bad match table is the only video on using with correct explanation using this method thanks from bottom of my ❤️
Thank you for your explaination. It was very clear to understand.
it's always the people with 100 subscribers making the best vids
simplified! thanks so much i love your way of teaching
Thank you for your amazing description.
Thank you for this excellent example, it was extremely easy to understand and I feel like I can write my own implementation after just one watch. Can you please write all my course textbooks? Lol
Thanks bro.Was searching for such an expln!
very good explaination...... plzz upload some more such videos.....
Amazing explanation! Thank youu!
thanks. good explanation. I understand it better now.
that was extremely creative. please keep on.
very cool algorithm, works pretty fast and it's simple
Great tutorial. I really appreciate it
really good explanation. thanks mate
Please correct me if I am wrong, but at 4:58 it is mentioned that we shift by 5 because of H wrong? Shouldn't we shift by 5 because the letter "S" that is not in our Bad-Table-List and thereby shift with the "*" value that tells us to shift by 5? It comes to the same amount in this example of shifting but if H had another value than 5 it would have been wrong. Because in the other cases we also shifted by the value of the letter above that didn't match our pattern at that point (H not T -> shift by T; H not O -> shift by O; and so on).
As said before, if I am mistaken or didn't understand it right please correct me on this.
You always look up the first character you attempted to match for a given alignment. Not the character that caused the mismatch. Therefore we lookup H at 4:58. This is consistent with the rest of the alignments.
@@mikeslade8772 Oh ok, then I did misunderstand that part. Thank you for clarifying it
This really helped me. Thanks!
Mike Slide blessed us with his amazing understanding of Horspool Algorithm, but I wonder, what is Mike doing today?
Mike is at the height of his powers, developing algorithms that go unseen to the naked eye, yet influence us all cerebrally, sub-consciously. Little is known about Mike Slade, some say he has no true bodily form and is a mere cloud of knowledge surrounding Horspool Algorithms, others say he is a simple fellow from the Shire, going about his merry way in this life, educating others and shunning fame. Lest, should we investigate further? Or be captured by thine curiosity? Tantalized by the unknown? I know which path I shall walk fellow TH-camr, join me in bathing in the unknown.
I just dont understand 1 step, why when you had your first mismatch you looked to the text and moved 1, but when you hit S, you looked for H because it was the length, or something like that? Can someone explain to me when i look to the text, and when i look to the table
What if the pattern was aaaa, and the generated table would be just one shift for a. Then if I wanted to compare it to the text axaaaabb, then the mismatch for x in the text would make the pattern shift 4 instead of 2(and we would miss the match)?
Nope here the first character checked is "a" so we will shift "1" time check the video at 5.10 :)
As far as i understand, the best case time complexity should be O(n/m), right?
thank you sir..this was really helpful
thank for this explanation :)
fantastic explaination, thanks!
whats the different between boyer moore horspool and boyer moore?
Thanks, great explanation!
Great video, thanks!
good explanation, thanks
very good, thanks!
great video.thank you
Hi, I am sorry I am digging up the subject, but one little think about the case that can have exactly n mismatches even m is greater than 0. This is a case when the implementations meets the users :). The case is simply when the pattern does not exists in entire source string. So practically it will be then
Success
- Mismatch(n-m) times
- Success at (n-m) +1
complexity: (((n-m) +1) x m)
Fail
- Mismatch(n) times
- Fail at (n)
complexity: (n)
Such fails are also costs for the alghoritm if it is exposed to user. Somtimes it is useful to know them, especially when you exposes a public service
From the hacking perspective if only length of the source string is known as "n" and the input pattern length is "m" then finding pattern complexity would be (S x n) + (((n-m) +1) x m)
where S will be a permutation of length of possible single characters with all possible lengths of patterns them-self. ;)
thank you that was very helpful hearts and kisses 😘👍
This isn't the Horspool variant of Boyer Moore is it? It's just the regular Boyer Moore algorithm...
it helps a lot, thank you
sir, how best case is O(m/n) ?
it will be n/m, he told wrong !!!!
Good explanation ,Than you
Thank you! it helps alot!
is that final index in the shift table used when the character that is landed on in searched string is all other cases other than the chars listed
Sorry, I have a question.
At the second alligment, the S doesn't match the O. So I have to look in the table for S, there isn't, so shift by 5. In the video you look for H. Same result, but I think the process is wrong. Isn't it?
No. When there is a mismatch at a given alignment, the rightmost character of the current alignment is looked up, not the character where the mismatch occurred. Hence, the 'h' was looked up rather than the 's' ;)
Thanks a lot! :')
Thanks
nice explanation
couldn't I just build the Bad-Match-Table from right to left/backwards to avoid updating letters?
The adjustment after mismatching S at 5:04 seems odd. Let's say the pattern is THOTH instead of TOOTH, this does not affect the adjustment value for S, since S is still not in the pattern. But shifting by 5 in case of THOTH will potentially miss a match, e.g. the text could be TRUSTHOTH..., am I missing something?
Checked other video, it seems that the index character used to look up the skip table should be the right most character in the text at the current alignment, which may or may not be the right most character in the pattern. Using the mismatched character to look up skip table will not handle repeating pattern like THOTH correctly.
@@KingKong-js5ql You need to construct a DIFFERENT bad match table if changing the pattern.
An explanation of why this works would be useful.
good video thanks
best of the best
the best!
What if the pattern is TOOTHT? Last character is the same as first, so the value for T becomes 0 or 6? Which means either no shift or 6 shifts. In each case, the algorithm fails, I think.
You have to calculate length - index - 1 for each character, except for the last one in the pattern. So the value for T would be 5 for the fisrt T, then overwritten to 2 for the second T and kept 2 for the last T, because this is the last character of the pattern. So the value for T would be 2.
Great video! I have one question: How did H get the value of 5?
H is the last letter from the pattern and because that, has the value of the length of the pattern
but that applies only when the last letter exists once in the pattern
@Ahmed Hammami Letter H is the last letter in the pattern, and thus it gets the value of the length of the pattern, if not defined otherwise. For example, in the pattern: AIRPLANE, the last letter E, gets the value of 8.
Bro can you tell why the logic works?
Very well explained, thank you.
Thanks!
how did H became 5?
This is clever.
thank you
How to approach for Bad character and
good suffix
Thank you for the video. Now everything is clear. However, I still have a question. Let's say that we have:
truoth... (string )
toath (pattern)
TABLE:
h = 5
t = 1
a = 2
o = 3
* = 5
The first shift is obviously equal to 1.
But what is the second, 5 (assignet to 'h') or 3 (assignet to 'o')?
thank you :) !!!
First of all, thanx for the video ! But I have a question too.
In your case when S doesn't match O , the rightmost character is looked up, right? You have mentioned that in a reply.
But if given text is 'ATCGTGACTGTAATGATGAGAGGTAATGTCG' and the pattern is 'GAGAG',
your method cannot find the pattern matching because it skips the pattern in the text. How do you explain that?
I have tried the algorithm on the problem you gave here, and it does find the pattern when I try it. What does your table look like? I have G = 2, A = 1 and * = 5
This comment is pretty old but maybe others experience such an issue with their code.
Things you should check to ensure your algorithm works right:
1) Did you set up the correct shift table?
Many people do mistakes at the point where you have patterns like:
HAHAH -> the last character is H but you cannot simply set it to 0 using the formula he mentioned in the video!
Watch it again and listen careful to 4:02 !
Do not overwrite the value of the last character if it already exists in your table!
2) Do you really shift correctly?
Often people just do:
GACTG
GAGAG
-> well, T is not equal to A ... lets just search for T inside the table !! NOO !!! DONT DO THIS!! xD
He also told you how to do it right (listen to 4:50), search for the first character that matched.
This means at this point we have to search for G inside our table.
>>>>>>>>>
I think "2)" will solve your problem.
G matched first -> G in table -> shift = 2
Step 3:
CTGTAATGATGAGAGGTAATGTCG
GAGAG
-->> G != A -> A in table -> shift = 1
Step 4:
TGTAATGATGAGAGGTAATGTCG
GAGAG
-->> G != A -> A in table -> shift = 1
Step 5:
GTAATGATGAGAGGTAATGTCG
GAGAG
-->> T != G -> T not in table -> shift = 5
Step 6:
GATGAGAGGTAATGTCG
GAGAG
--> A != G -> A in table -> shift = 1
Step 7:
ATGAGAGGTAATGTCG
GAGAG
-> G = G
-> A = A
-> G = G
-> T != A
-->> G matched first -> G in table -> shift = 2
Step 8:
GAGAGGTAATGTCG
GAGAG
-> G = G
-> A = A
-> G = G
-> A = A
-> G = G
-->> EVERYTING MATCHES -> PATTERN FOUND! -> shift = 5
Step 9:
GTAATGTCG
GAGAG
-->> T != G -> T not in table -> shift = 5
Step 10:
GTCG
GAGAG
-->> Pattern Doesnt fit in source anymore -> finish
CONCLUSION: pattern found (see step 8)
Hope I could help someone with that :)
Thank you so much, there seems to be two different levels of Boyer-Moore algorithms. The basic one as this video taught, and an advanced one with good suffix and bad character.
Brilliant explanation!
Could you help me with the following question:
truoth... (string )
toath (pattern)
TABLE:
h = 5
t = 1
a = 2
o = 3
* = 5
The first shift is equal to 1.
But what is the second, 5 (assignet to 'h') or 3 (assignet to 'o')?
awesome
What if the text was TRUSTOOTH? Seems like your explanation is not correct
thanks
I love that
I'm going to name my son dwongleberryhead junior
boyer moore and horspool algorithms are different
the video you explained is horspool's algorithm
boyer moore is littler different please change the title to "horspool algorithm"
Boyer-Moore-Horspool and Horspool are synonyms: en.m.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm
This is so painfully wrong I'm saddened to see so many people blindly believing it's an actual representation of the algorithm.
how's it wrong?
Explain how it's wrong..I am serious asking
@@UnknownGamer-lw7zp Sorry, ,dude, this was 4 years ago. I can't even recall what this was all about.
Thanks/!
I am an antelope
who uses hard toothbrushes?
Thanks bro
😢
For all those out there watching this and actually can think for yourself instead of mindlessly believing in everything. This video is wrong. It would not work if the combination was for example THOTH. Main point is, the increment should be done from the current position in the text, not the end of the chunk. I.e. the +5 should be counted from S at 4:55, not from H, therefore shifting to HARDT instead of ARDTO. OP should take down this video given how much misinformation it is propagating.
By 'if the combination was for example THOTH' do you mean if the pattern was THOTH instead of TOOTH? In that case you are correct it will not work as you need to construct a DIFFERENT bad match table.
Shifting to HARDT instead of ARDTO at 4:55 is pointless for the 'TOOTH' pattern. Why bother comparing the leftmost H in HARDT with the leftmost T in TOOTH?
@@mikeslade8772 Thanks for responding! Let's walk through this algorithm together. If you used THOTH and the text was TRUSTHOTHTOOTHBRUSHES, the table will be the same because we always take the rightmost value of the alphabet in the pattern. So [T:1, O:2, H:5, ' ':5]. If we apply your way, we will get to the step where we are comparing T *RUSTH* OTHTOOTHBRUSHES to THOTH in the pattern. If we shift 5 space like what you did, we immedidately jump to comparing TRUSTH *OTHTO* OTHBRUSHES to THOTH. Your algorithm fails to find the pattern. The correct algorithm is to apply +5 to the current mismatch. So since the mismatch is at S, we should instead shift to TRUS *THOTH* TOOTHBRUSHES and you get the correct result. The whole point of the horspool algorithm is to match up the current misaligned character in the text and pattern, your proposed version simply doesn't do that. To give another example, let T be TRUSTHARDTOOTHBRUSHES and P be UBEST, initial comparison is *TRUST* HARDTOOTHBRUSHES and UBEST. What we want is to match up the U. By your method we are going to count 4 from T to get the new endpoint, which will give TRUS *THARD* TOOTHBRUSHES and it does not align them at all! Instead the count should the current mismatch, which is U, so we get TR *USTHA* RDTOOTHBRUSHES. Hope this helps you see your error.
@@mikeslade8772 Also would like to point out that it does not make sense to say doing xxx is pointless for a specific pattern. The whole point of an algorithm is to propose a general solution for a class of problems. Just because it is not useful in this pattern doesn't mean it shouldn't be done.
@@Kuro-uc4jp you have constructed the bad match table incorrectly. H is not 5. The rightmost character in the pattern is the length UNLESS already defined (as shown on the slides). H should therefore be 3 for the pattern THOTH. ( length - index - 1 = 5 - 1 - 1 = 3).
@@Kuro-uc4jp Hope this helps you see your error.
Yalpalıyor
can you speak in english?
can you speak in indonesia?
This video was too long. Halfway through it, I got hungry so I left it playing and went to the kitchen to fix my self a sandwich. But then I found out that I'm out of mayonnaise so I went to a store. There, I saw the most beautiful woman I have ever seen in my whole life. But I'm really a shy person so I took up a three-year personality development course so I can introduce my self. She was very friendly and all, but unfortunately, she has a boyfriend. So I said, all good, I'm a mature person. I want the best for her and I harbor no illusion that I am the best person for her and she seems happy with her boyfriend, so I did not bother her anymore. But we kept in touch and we became friends and I got over my crush on her. Then she broke up with her boyfriend, we drank some alcohol because of it, I told her she'll be fine and I wished her well. I still think she's the most beautiful woman in the world, but like I said, I am over my crush on her. It was like five years already when I first saw her. Besides, I am quiet happy with the friendship I developed with her. It was more important than a crush. So we kept hanging out, drinking, having coffee, and all. I had a girlfriend, she started dating other guys. My girlfriend wants to live some other life without me in it, so I said, okay, I want the best for you and I want you to pursue your happiness. My lady friend and I drank alcohol about it, and she gave me the same advice I gave her when she was in that position and I became okay with the breakup immediately. But we were really drunk, so she spent the night in my apartment. I only have one bed, so you know what that means: She took the bed and I slept on the couch. But on the couch, I really can't sleep. Something was bothering me. So I tossed and turned for about three hours, then I finally can't take it anymore, I stood up and went straight to my room where she's sleeping. I approached the bed, gently sat on it and I reached for her shoulder to pull her closer to me. She stirred and woke up. She asked what's up. I told her, you know, the first time I saw you, I was watching a video and left it playing to get my self a sandwich then went to the store to get some mayo then I got distracted by life that I forgot to finish the video. She said, you know what, I've been wondering about a weird noise in your night drawer. So we opened that drawer, and lo and behold, there's my phone and this video still has two minutes of play time on it.
But like this comment really
@@shothecrow1740 best way to roast your brother really
This is wrong. You won't skip just as long as the pattern length.
perfect explanation! thanks alot!
Thanks