DNA sequence

import fileinput

with fileinput.input(['-']) as input:
    seq = input.readline().rstrip()
    q = int(input.readline().rstrip())
    for _ in range(q):
        f = False
        subseq = input.readline().rstrip()
        s = subseq + '%' + seq
        n, z = len(s), [0]*len(s)
        zbl, zbr, z[0] = 0, 0, n
        for i in range(1, n):
            if i < zbr:
                k = i - zbl
                if z[k] < zbr - i:
                    z[i] = z[k]
                    continue
                zbl = i
            else:
                zbl = zbr = i
            while zbr < n and s[zbr-zbl] == s[zbr]:
                zbr += 1
            z[i] = zbr - zbl
            if z[i] == len(subseq):
                f = True
                break
        m = 'YES' if f else 'NO'
        print(m)

Test 1

Verdict: TIME LIMIT EXCEEDED