DNA sequence

import fileinput

seen = {}

with fileinput.input(['-']) as input:
    seq = input.readline().rstrip()
    q = int(input.readline().rstrip())
    for _ in range(q):
        subseq = input.readline().rstrip()
        if subseq in seen:
            print(seen[subseq])
            continue
        f = False
        s = subseq + '$' + seq
        n = len(s)
        lenss = len(subseq)
        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
                if z[i] == lenss:
                    f = True
                    break
                r -= 1
            else:
                k = i - l
                if z[k] < r-i+1:
                    z[i] = z[k]
                    if z[i] == lenss:
                        f = True
                        break
                else:
                    l = i
                    while r < n and s[r-l] == s[r]:
                        r += 1
                    z[i] = r - l
                    if z[i] == lenss:
                        f = True
                        break
                    r -= 1
        msg = 'YES' if f else 'NO'
        print(msg)
        seen[subseq] = msg

Test 1

Verdict: TIME LIMIT EXCEEDED