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

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_hashes(seq):
    for i in range(len(seq)):
        hashes[1].add(hash(seq[i]))
    lseq = len(seq)
    for j in range(2, 11):
        prev_hash = None
        for i in range(0, lseq-j+1):
            if prev_hash is None:
                h = hash(seq[i:i+j])
                hashes[j].add(h)
                prev_hash = h
            else:
                #h = prev_hash * P - VALS[seq[i+j]] * pow(P, j) + VALS[seq[i]]
                h = hash(seq[i:i + j])
                hashes[j].add(h)
                prev_hash = h


with fileinput.input(['-']) as input:
    seq = input.readline().rstrip()
    q = int(input.readline().rstrip())
    compute_hashes(seq)
    for _ in range(q):
        subseq = input.readline().rstrip()
        subseq_hash = hash(subseq)
        if subseq_hash in hashes[len(subseq)]:
            print('YES')
        else:
            print('NO')

#print(time.time() - a)

Test 1

Verdict: TIME LIMIT EXCEEDED