DNA sequence

import fileinput

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

Test 1

Verdict: TIME LIMIT EXCEEDED