Re^4: Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (And is there an alternative that does?)

Okay? So, we have your table, the original haystack and the needle you used:

00000110 needle offset 14
00001010 needle offset 0
00001101 needle offset 15
00010100 needle offset 1
00011010 needle offset 16
00101001 needle offset 2
00101010 needle offset 7
01000001 needle offset 12
01001010 needle offset 5
01010000 needle offset 10
01010010 needle offset 3
01010100 needle offset 8
10000011 needle offset 13
10010101 needle offset 6
10100000 needle offset 11
10100101 needle offset 4
10101000 needle offset 9

0000111010011100101110110111000111101011110011111011111110000000100010
+0100001010010101000001101000110010011000101101010110011011000000
000010100101010000011010
[download]

We've compared the needle at the first position of the haystack and it doesn't match. Now what?

Which group of 8 bits from the haystack do we lookup in the table?
And how do we translate the offset at which that pattern was found in the needle; into a number of bits to shift the needle?

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority". I'm with torvalds on this

In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

Comment on Re^4: Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (And is there an alternative that does?) Download Code

Replies are listed 'Best First'.
Re^5: Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (And is there an alternative that does?) by Anonymous Monk on Apr 05, 2015 at 19:21 UTC
The first group to inspect is at position (needle_len - 8): 10111011. That does not appear in the needle, so apply the maximum shift, which is 17 (needle_len - 8 + 1). Were it present in the needle, then the shift would've been (needle_len - 8 - offset), followed by compare.	[reply]
Re^6: Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (And is there an alternative that does?) by BrowserUk (Patriarch) on Apr 05, 2015 at 20:29 UTC
Did I go wrong some where cos it seems to miss it. 00000110 needle offset 14 00001010 needle offset 0 00001101 needle offset 15 00010100 needle offset 1 00011010 needle offset 16 00101001 needle offset 2 00101010 needle offset 7 01000001 needle offset 12 01001010 needle offset 5 01010000 needle offset 10 01010010 needle offset 3 01010100 needle offset 8 10000011 needle offset 13 10010101 needle offset 6 10100000 needle offset 11 10100101 needle offset 4 10101000 needle offset 9 The first group to inspect is at position (needle_len - 8): 10111011. That does not appear in the needle, so apply the maximum shift, which +is 17 (needle_len - 8 + 1). Were it present in the needle, then the shift would've been (needle_le +n - 8 - offset), followed by compare. ???????? ???????? ???????? ??? +????? ???????? ???????? ???????? ???????? 0000111010011100101110110111000111101011110011111011111110000000100010 +0100001010010101000001101000110010011000101101010110011011000000 + 000010100101010000011010 Not there; max. shift 17 000010100101010000011010 Not there +17 000010100101010000011010 Not there + +17 0000101001010100000 +11010 Not there +17 00 +0010100101010000011010 In table +12 + 000010100101010000011010 Not there +17 + 000010100101010000011010 Not there +17 + 000010100101010000011010 +Not there +17 [download] With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". I'm with torvalds on this In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked code	[reply] [d/l]
Re^7: Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (And is there an alternative that does?) by Anonymous Monk on Apr 05, 2015 at 21:01 UTC
In table +12 => Shift by 4 (24-8-12).	[reply]
Re^8: Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (Thank you Anonymonk + others.) by BrowserUk (Patriarch) on Apr 08, 2015 at 05:32 UTC
Re^9: Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (Thank you Anonymonk + others.) by Anonymous Monk on Apr 08, 2015 at 17:14 UTC
Some notes below your chosen depth have not been shown here
Re^8: Why Boyer-Moore, Horspool, alpha-skip et.al don't work for bit strings. (And is there an alternative that does?) by BrowserUk (Patriarch) on Apr 05, 2015 at 21:30 UTC