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 = {
    1: set(),
    2: set(),
    3: set(),
    4: set(),
    5: set(),
    6: set(),
    7: set(),
    8: set(),
    9: set(),
    10: set(),
}


with fileinput.input(['-']) as input:
    seq = input.readline().rstrip()
    q = int(input.readline().rstrip())
    ls = len(seq)
    subseqs = []
    for _ in range(q):
        subseq = input.readline().rstrip()
        subseqs.append(subseq)
    for subseq in sorted(subseqs, key=len):
        lss = len(subseq)
        if lss > ls:
            print('NO')
            continue
        x = False
        if lss >= 8:
            for i in range(1, 8):
                if subseq[0:i] in seen_no[i]:
                    x = True
                    break
        if x:
            print('NO')
            continue
        subseq_hash = hash(subseq)
        if subseq_hash in hashes[lss]:
            print('YES')
        else:
            f = False
            prev_hash = None
            for i in range(lhs[lss], ls-lss+1):
                if prev_hash is None:
                    h = hash(seq[lhs[lss]:lhs[lss]+lss])
                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[lss].add(subseq)
    #print(hashes)

#print(time.time() - a)

Test 1

Verdict: TIME LIMIT EXCEEDED