diff options
Diffstat (limited to 'ass1/binary_boyermoore.py')
| -rw-r--r-- | ass1/binary_boyermoore.py | 27 |
1 files changed, 27 insertions, 0 deletions
diff --git a/ass1/binary_boyermoore.py b/ass1/binary_boyermoore.py new file mode 100644 index 0000000..1d60f52 --- /dev/null +++ b/ass1/binary_boyermoore.py @@ -0,0 +1,27 @@ +txt = "xpbctbxabacbxtbpqa" +pat = "tbapxab" +m = len(pat) +n = len(txt) +R = [m for _ in range(0, 26)] + +def alpha_number(char): + return ord(char) - 97 + +for i in range(m): + R[alpha_number(pat[i])] = i + +j = 0 +while j < n-m: + for i in range(m-1, -1, -1): + print(j) + match = pat[i] == txt[j+i] + if match: + pass + # print(i) + else: + mismatched = txt[j+i] + shift = i-R[alpha_number(mismatched)] + j += max(1, shift) + if j > n-m: + break +print(R)
\ No newline at end of file |