1 def horsepool(S: str, P: str) -> tuple:
2 n, m, M = len(S), len(P), 26
3 shift_table = [m for _ in range(M)]
4 for i in range(m - 1):
5 shift_table[ord(P[i]) - ord('A')] = m - i - 1
6 pos, ans, flag = 0, [], False
7
8 while pos <= (n - m):
9 j = m - 1
10 while j >= 0 and S[pos + j] == P[j]:
11 j -= 1
12 if j == -1:
13 flag = True
14 ans.append(pos)
15 pos += m
16 else:
17 pos += shift_table[ord(S[pos + m - 1]) - ord('A')]
18 if not flag:
19 print("Not find")
20 return flag, ans, shift_table
21
22
23 if __name__ == '__main__':
24 S = "AGCAATGAA"
25 P = "ATGAA"
26 flag, pos, table = horsepool(S, P)
27 print(flag)
28 print(pos)
29 print(table)
