Алгоритм Рабина-Карпа

def simple_find(s, sub):
    N = 0
    for pos in range(0, len(s) - len(sub) + 1):
        N += 1
        flag = True
        for i in range(len(sub)):
            if s[pos+i] != sub[i]:
                flag = False
                break
            N += 1
        if flag:
            print(pos)
    print('Потребовалось N=%d операций'%(N))



def rabin_karp_find(s, sub):
    N = 0
    h_sub = sum(ord(c) for c in sub)
    h = sum(ord(c) for c in s[:len(sub)])
    for pos in range(0, len(s) - len(sub)):
        N += 1
        if h != h_sub: # не совпали хеш-функции подстроки и кусочка строки
            h = h - ord(s[pos]) + ord(s[pos + len(sub)])  # перевычисление хеш-функции
            continue
        h = h - ord(s[pos]) + ord(s[pos + len(sub)])  # перевычисление хеш-функции
        flag = True
        for i in range(len(sub)):
            if s[pos+i] != sub[i]:
                flag = False
                break
            N += 1
        if flag:
            print(pos)
    print('Потребовалось N=%d операций'%(N))

#s = 'АТАГАТАЦАТАГАТАЦАТАГАТАГАЦАТА'
s = ('A'*10 + 'T')*100 + 'A'*11 + 'T'
simple_find(s, 'A'*11)
rabin_karp_find(s, 'A'*11)