DNA sequence

import fileinput

seen = {}

with fileinput.input(['-']) as input:
    seq = input.readline().rstrip()
    q = int(input.readline().rstrip())
    subseqs = []
    for _ in range(q):
        subseqs.append(input.readline().rstrip())
    sss = subseqs.copy()
    subseqs.sort(key=len, reverse=True)
    for subseq in subseqs:
        if subseq in seen:
            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'
        if msg == 'NO':
            seen[subseq] = msg
        else:
            for i in range(1, len(subseq)+1):
                seen[subseq[0:i]] = 'YES'
    for s in sss:
        print(seen[s])

Test 1

Verdict: TIME LIMIT EXCEEDED