blob: 1d60f521e7547c5ef98e833043bb064f9bca4630 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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)
|
