DNA sequence

import fileinput
from math import pow
import time

VALS = {
    'A': 0,
    'C': 1,
    'T': 2,
    'G': 3
}
P = 5

hashes = {
    1: [],
    2: [],
    3: [],
    4: [],
    5: [],
    6: [],
    7: [],
    8: [],
    9: [],
    10: []
}

def hash(q):
    _hash = 0
    lq = len(q)
    for i in range(lq):
        _hash += VALS[q[i]] * pow(P, lq-i-1)
    return _hash

a = time.time()

lh = 0

seq = ''


with fileinput.input(['-']) as input:
    seq = input.readline().rstrip()
    q = int(input.readline().rstrip())
    ls = len(seq)
    for _ in range(q):
        subseq = input.readline().rstrip()
        subseq_hash = hash(subseq)
        lss = len(subseq)
        lh = len(hashes[lss])
        if subseq_hash in hashes[lss]:
            print('YES')
        else:
            f = False
            prev_hash = None
            for i in range(lh, ls-lss):
                if prev_hash is None:
                    h = hash(seq[lh:lh+lss])
                    hashes[lss].append(h)
                    lh += 1
                    prev_hash = h
                else:
                    h = prev_hash * P - VALS[seq[lh-1]] * pow(P, lss) + VALS[seq[lh + lss - 1]]
                    hashes[lss].append(h)
                    lh += 1
                    prev_hash = h
                if h == subseq_hash:
                    f = True
                    break
            print('YES' if f else 'NO')

print(time.time() - a)

Test 1

Verdict: TIME LIMIT EXCEEDED