# Boyer–Moore–Horspool String Matching
# ord('A') : ASCII code number of 'A'

import string

T='GCAtCGCAGAgAGTATacaGTACG'          # Text
P='GCAGAGAG'                      # Pattern
'''
T='agatacgatatatac'
P='atata'
'''
n=len(T)                          # Length of T and P
m=len(P)
d=[m]*26                          # HoBc table (A to Z)

T=T.upper()                       # Make all characters in T and P to uppercase
P=P.upper()

# Preprocessing: Make HoBc table
# Rightmost position of A,C,G,T from m-1 in P
i=m-2
while i>=0:
    if d[ord(P[i])-ord('A')]==m:
        d[ord(P[i])-ord('A')]=m-i-1
    i=i-1

# Searching
pos=0 # from 0
while pos<=n-m: # to n-m
    j=m-1 # pattern index
    while j>=0 and T[pos+j]==P[j]: # match T and P
        j=j-1
    if j<0: # if found P in T
        print pos
    pos=pos+d[ord(T[pos+m-1])-ord('A')] # shift Pattern to right