DNA sequence

import fileinput
from math import pow
import time

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

hashes = {
    1: set(),
    2: set(),
    3: set(),
    4: set(),
    5: set(),
    6: set(),
    7: set(),
    8: set(),
    9: set(),
    10: set()
}

lhs = {
    1: 0,
    2: 0,
    3: 0,
    4: 0,
    5: 0,
    6: 0,
    7: 0,
    8: 0,
    9: 0,
    10: 0
}

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 = ''

seen_no = set()


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()
        lss = len(subseq)
        if lss > ls:
            print('NO')
            continue
        subseq_hash = hash(subseq)
        lh = lhs[lss]
        if subseq_hash in hashes[lss]:
            print('YES')
        else:
            f = False
            prev_hash = None
            for i in range(lh, ls-lss+1):
                if prev_hash is None:
                    h = hash(seq[lh:lh+lss])
                    hashes[lss].add(h)
                    lhs[lss] += 1
                    prev_hash = h
                else:
                    h = prev_hash * P - VALS[seq[lhs[lss]-1]] * pow(P, lss) + VALS[seq[lhs[lss] + lss - 1]]
                    hashes[lss].add(h)
                    lhs[lss] += 1
                    prev_hash = h
                if h == subseq_hash:
                    f = True
                    break
            print('YES' if f else 'NO')
            if not f:
                seen_no.add(subseq)
    print(lhs)
    #print(hashes)


print(time.time() - a)

Test 1

Verdict: TIME LIMIT EXCEEDED