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: []
}

seen = {}

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()

def compute_hash(seq, j):
    i = len(hashes[j])
    if not hashes[j]:
        h = hash(seq[0:j])
        hashes[j].append(h)
    else:
        prev_hash = hashes[j][-1]
        h = prev_hash * P - VALS[seq[i-1]] * pow(P, j) + VALS[seq[i+j-1]]
        hashes[j].append(h)
    return


with fileinput.input(['-']) as input:
    seq = input.readline().rstrip()
    q = int(input.readline().rstrip())
    for _ in range(q):
        subseq = input.readline().rstrip()
        subseq_hash = hash(subseq)
        ls = len(subseq)
        f = False
        while True:
            if subseq_hash not in hashes[ls]:
                if len(hashes[ls]) != len(seq) - ls + 1:
                    compute_hash(seq, ls)
                else:
                    break
            else:
                f = True
                break
        msg = 'YES' if f else 'NO'
        print(msg)

print(time.time() - a)

Test 1

Verdict: TIME LIMIT EXCEEDED