Problem:


String Search

  Determine whether a text T includes a pattern P. Your program should answer for given queries consisting of P_i.

Input

  In the first line, a text T is given. In the second line, an integer Q denoting the number of queries is given. In the following Q lines, the patterns P_i are given respectively.

Output

  For each question, print 1 if the text includes P_i, or print 0 otherwise.

Constraints

  
 1 ≤ length of T ≤ 1000000 

  
 1 ≤ length of P_i ≤ 1000 

  
 1 ≤ Q ≤ 10000 

  
The input consists of alphabetical characters and digits

Sample Input 1

aabaaa
4
aa
ba
bb
xyz

Sample Output 1

1
1
0
0



Sample input:
aabaaa
4
aa
ba
bb
xyz


Sample output:
1
1
0
0

Submission status: Accepted

Solution code:
base = 127
mask = (1 << 32) - 1
def calc_hash(f, pl, tl):
    dl = tl - pl
    tmp = set()
    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + f[i]) & mask
    for i in range(dl):
        tmp.add(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.add(e)
    return tmp
t = tuple(ord(c) for c in input())
tl = len(t)
q = int(input())
h = dict()
c = dict()
a = []
for _ in range(q):
    p = input()
    if p in c:
        a.append(c[p])
        continue
    p = tuple(ord(c) for c in p)
    pl = len(p)
    if pl > tl:
        a.append(0)
        continue
    bs = min(19, pl)
    keys = calc_hash(p, bs, pl)
    if bs not in h:
        h[bs] = calc_hash(t, bs, tl)
    a.append(1 if keys.issubset(h[bs]) else 0)
print('\n'.join(map(str, a)))

Submission status: Accepted

Solution code:
base = 127
mask = (1 << 32) - 1
def calc_hash(f, pl, tl):
    dl = tl - pl
    tmp = set()
    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + f[i]) & mask
    for i in range(dl):
        tmp.add(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.add(e)
    return tmp
t = tuple(ord(c) for c in input())
tl = len(t)
q = int(input())
h = dict()
c = dict()
a = []
for _ in range(q):
    p = input()
    if p in c:
        a.append(c[p])
        continue
    p = tuple(ord(c) for c in p)
    pl = len(p)
    if pl > tl:
        a.append("0")
        continue
    bs = min(19, pl)
    keys = calc_hash(p, bs, pl)
    if bs not in h:
        h[bs] = calc_hash(t, bs, tl)
    a.append("1" if keys.issubset(h[bs]) else "0")
print('\n'.join(a))

Submission status: Accepted

Solution code:
base = 127
mask = (1 << 32) - 1
def calc_hash(f, pl, tl):
    dl = tl - pl
    tmp = set()
    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + f[i]) & mask
    for i in range(dl):
        tmp.add(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.add(e)
    return tmp
t = tuple(ord(c) for c in input())
tl = len(t)
q = int(input())
h = dict()
c = dict()
a = []
for _ in range(q):
    p = input()
    if p in c:
        a.append(c[p])
        continue
    p = tuple(ord(c) for c in p)
    pl = len(p)
    if pl > tl:
        a.append("0")
        continue
    bs = min(19, pl)
    keys = calc_hash(p, bs, pl)
    if bs not in h:
        h[bs] = calc_hash(t, bs, tl)
    a.append("1" if keys <= h[bs] else "0")
print('\n'.join(a))

Submission status: Accepted

Solution code:
from collections import Counter
from math import floor, ceil, log
from heapq import heapreplace, heappush
import time


class TreeIndex:

    class Node:
        __slots__ = ('level', 'keys', 'values', 'keylen', '_cache', '_cacheq')

        def __init__(self, level):
            self.level = level
            self.values = []
            self.keys = {}
            self.keylen = 2 ** self.level
            self._init_cache()

        def add(self, text, value):
            def _add(node, t):
                if len(t) == 0:
                    node.values.append(value)
                    return node

                pre = t[:node.keylen]
                post = t[node.keylen:]
                if pre not in node.keys:
                    node.keys[pre] = self.__class__(node.level+1)
                return _add(node.keys[pre], post)

            node = self._get_cache(text)
            if node is not None:
                _add(node, '')
            else:
                self._set_cache(text, _add(self, text))

        def index(self, text):
            def _index(node, t):
                if len(t) == 0:
                    return node

                pre = t[:node.keylen]
                post = t[node.keylen:]
                if pre in node.keys:
                    return _index(node.keys[pre], post)
                else:
                    return None

            node = self._get_cache(text)
            if node is not None:
                return node.values
            else:
                node = _index(self, text)
                if node is not None:
                    self._set_cache(text, node)
                    return node.values
                return []

        def __contains__(self, text):
            if len(text) > self.keylen:
                pre = text[:self.keylen]
                post = text[self.keylen:]
                return (pre in self.keys and post in self.keys[pre])
            else:
                return any(key.startswith(text) for key in self.keys)

        def _init_cache(self):
            self._cache = {}
            self._cacheq = []

        def _set_cache(self, text, node):
            if text not in self._cache:
                if len(self._cacheq) > 65535:
                    _, txt = heapreplace(self._cacheq, (time.clock(), text))
                    del self._cache[txt]
                else:
                    heappush(self._cacheq, (time.clock(), text))
                self._cache[text] = node

        def _get_cache(self, text):
            if text in self._cache:
                return self._cache[text]
            else:
                return None

        def __str__(self):
            return ('(' + ','.join(["{}->{}".format(k, v)
                                   for k, v in self.keys.items()]) + ')')

    def __init__(self, text):
        self._keylen(text)
        self._create_index(text)

    def _keylen(self, text):
        chars = Counter(list(text))
        ent = 0.0
        total = len(text)
        base = len(chars) + 1
        for c, cnt in chars.items():
            p = cnt / total
            ent -= p * log(p, base)
        self.keylen = max(2 ** ceil(10 * (1 - ent)) - 1, 3)
        # print(ent, self.keylen)

    def _create_index(self, text):
        tree = self.Node(0)
        length = len(text)
        for i in range(length):
            tree.add(text[i:i+self.keylen], i)
        self.tree = tree
        self.text = text
        # print('key length = {}'.format(self.keylen))
        # print(self.tree)

    def match(self, search_text):
        def _match_partial(lo, hi):
            # print('match partial', lo, hi, search_text[lo:hi])
            split = self.keylen
            if search_text[lo+split:hi] in self.tree:
                for i in self.tree.index(search_text[lo:lo+split]):
                    if (self.text[i+split:i+hi-lo]
                            == search_text[lo+split:hi]):
                        yield i

        def _match(lo, hi):
            length = hi - lo

            if length == self.keylen:
                # print('match index', lo, hi)
                return (i for i in self.tree.index(search_text[lo:hi]))

            if length < self.keylen*2:
                return _match_partial(lo, hi)

            mid = lo + length // 2
            pre = _match(lo, mid)
            post = _match(mid, hi)

            return _merge(pre, post, mid-lo)

        def _merge(idx1, idx2, shift):
            i2 = next(idx2)
            for i1 in idx1:
                while i1 + shift > i2:
                    i2 = next(idx2)
                if i1 + shift == i2:
                    # print('match!', i1, self.text[i1:i1+length], search_text)
                    yield i1

        length = len(search_text)
        if length < self.keylen:
            return search_text in self.tree

        # align by key length
        k = floor(log(length/self.keylen, 2))
        b = self.keylen * 2**k
        if length - self.keylen < b < length and k > 0:
            b = self.keylen * 2**(k-1)

        try:
            if b + self.keylen < length:
                match = _merge(_match(0, b), _match(b, length), b)
            else:
                match = _match(0, length)
            next(match)
            return True
        except StopIteration:
            return False


def run():
    s1 = input()
    n = int(input())

    index = TreeIndex(s1)
    for _ in range(n):
        s2 = input()
        if index.match(s2):
            print(1)
        else:
            print(0)


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
from collections import Counter
from math import floor, ceil, log
from heapq import heapreplace, heappush
import time


class TreeIndex:
    CACHESIZE = 65535

    class Node:
        __slots__ = ('level', 'keys', 'values', 'keylen')

        def __init__(self, level):
            self.level = level
            self.values = []
            self.keys = {}
            self.keylen = 2 ** self.level

        def add(self, text, value):
            if len(text) == 0:
                self.values.append(value)
                return self
            pre = text[:self.keylen]
            post = text[self.keylen:]
            if pre not in self.keys:
                self.keys[pre] = self.__class__(self.level+1)
            return self.keys[pre].add(post, value)

        def find(self, text):
            if len(text) == 0:
                return self
            pre = text[:self.keylen]
            post = text[self.keylen:]
            if pre in self.keys:
                return self.keys[pre].find(post)
            else:
                return None

        def __contains__(self, text):
            if len(text) > self.keylen:
                pre = text[:self.keylen]
                post = text[self.keylen:]
                return (pre in self.keys and post in self.keys[pre])
            else:
                return any(key.startswith(text) for key in self.keys)

        def __str__(self):
            return ('(' + ','.join(["{}->{}".format(k, v)
                                   for k, v in self.keys.items()]) + ')')

    def __init__(self, text):
        self.text = text
        self._init_cache()
        self._keylen()
        self._create_index()

    def _keylen(self):
        chars = Counter(list(self.text))
        ent = 0.0
        total = len(self.text)
        base = len(chars) + 1
        for c, cnt in chars.items():
            p = cnt / total
            ent -= p * log(p, base)
        self.keylen = max(2 ** ceil(10 * (1 - ent)) - 1, 3)

    def _create_index(self):
        self.tree = self.Node(0)
        length = len(self.text)
        for i in range(length):
            self.add(self.text[i:i+self.keylen], i)

    def _init_cache(self):
        self._cache = {}
        self._cacheq = []

    def _set_cache(self, text, node):
        if text not in self._cache:
            if len(self._cacheq) > self.CACHESIZE:
                _, txt = heapreplace(self._cacheq, (time.clock(), text))
                del self._cache[txt]
            else:
                heappush(self._cacheq, (time.clock(), text))
            self._cache[text] = node

    def _get_cache(self, text):
        if text in self._cache:
            return self._cache[text]
        else:
            return None

    def index(self, text):
        node = self._get_cache(text)
        if node is None:
            node = self.tree.find(text)

        if node is None:
            return []
        else:
            self._set_cache(text, node)
            return node.values

    def add(self, text, value):
        node = self._get_cache(text)
        if node is None:
            node = self.tree.add(text, value)
            self._set_cache(text, node)
        else:
            node.add('', value)

    def match(self, search_text):
        def _match_partial(lo, hi):
            split = self.keylen
            if search_text[lo+split:hi] in self.tree:
                for i in self.index(search_text[lo:lo+split]):
                    if (self.text[i+split:i+hi-lo]
                            == search_text[lo+split:hi]):
                        yield i

        def _match(lo, hi):
            length = hi - lo

            if length == self.keylen:
                return (i for i in self.index(search_text[lo:hi]))
            elif length < self.keylen*2:
                return _match_partial(lo, hi)

            mid = lo + length // 2
            pre = _match(lo, mid)
            post = _match(mid, hi)

            return _merge(pre, post, mid-lo)

        def _merge(idx1, idx2, shift):
            i2 = next(idx2)
            for i1 in idx1:
                while i1 + shift > i2:
                    i2 = next(idx2)
                if i1 + shift == i2:
                    yield i1

        length = len(search_text)
        if length < self.keylen:
            return search_text in self.tree

        # align by key length
        k = floor(log(length/self.keylen, 2))
        b = self.keylen * 2**k
        if length - self.keylen < b < length and k > 0:
            b = self.keylen * 2**(k-1)

        try:
            if b + self.keylen < length:
                match = _merge(_match(0, b), _match(b, length), b)
            else:
                match = _match(0, length)
            next(match)
            return True
        except StopIteration:
            return False


def run():
    s1 = input()
    n = int(input())

    index = TreeIndex(s1)
    for _ in range(n):
        s2 = input()
        if index.match(s2):
            print(1)
        else:
            print(0)


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
base = 127
mask = (1 << 32) - 1

def calc_hash(lstr, pl, tl):
    dl = tl - pl
    tmp = set()

    d = 1
    for _ in range(pl):
        d = (d * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + lstr[i]) & mask
    for i in range(dl):
        tmp.add(e)
        e = (e * base - d * lstr[i] + lstr[i + pl]) & mask
    tmp.add(e)
    return tmp


t = [ord(c) for c in input().strip()]
tl = len(t)
q = int(input())
ps = [input().strip() for _ in range(q)]
h = dict()
dic = dict()
a = []
for pp in ps:
    if pp in dic:
        a.append(dic[pp])
        continue
    p = [ord(c) for c in pp]
    pl = len(p)
    if pl > tl:
        a.append(0)
        continue
    bs = min(19, pl)
    keys = calc_hash(p, bs, pl)
    if bs not in h:
        h[bs] = calc_hash(t, bs, tl)
#    print("hb", keys, h[bs])
    a.append(1 if keys.issubset(h[bs]) else 0) #keysがh[bs]に含まれるか
    dic[pp] = a[-1]
print('\n'.join(map(str, a)))

Submission status: Accepted

Solution code:
from typing import Dict, List


def calc_hash(input_v: List[int], target_len: int, input_len: int) -> set:
    global base, mask
    diff_len = input_len - target_len
    hash_set = set()

    bit_mask = 1
    for _ in range(target_len):
        bit_mask = (bit_mask * base) & mask
    hash_v = 0
    for i in range(target_len):
        hash_v = (hash_v * base + input_v[i]) & mask
    for i in range(diff_len):
        hash_set.add(hash_v)
        hash_v = (hash_v * base - bit_mask * input_v[i]
                  + input_v[i + target_len]) & mask
    hash_set.add(hash_v)

    return hash_set


if __name__ == "__main__":
    base = 123  # Ascii code after 'z'
    mask = (1 << 32) - 1  # Mask.

    input_v = [ord(s) for s in input()]
    input_len = len(input_v)

    checked_dict: Dict[int, set] = {}
    num_target = int(input())

    for _ in range(num_target):
        target_v = [ord(s) for s in input()]
        target_len = len(target_v)
        if input_len < target_len:
            print(0)
            continue
        magic_len = min(19, target_len)  # Magic number to reduce calc time.
        key = calc_hash(target_v, magic_len, target_len)
        if magic_len not in checked_dict:
            checked_dict[magic_len] = calc_hash(input_v, magic_len, input_len)
        if key.issubset(checked_dict[magic_len]):
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys


def lms(t, i):
    return i > 0 and not t[i-1] and t[i]


def induced_sort(s, k, t, lmss):

    sa = [-1] * len(s)
    cbin = [0]*k

    for c in s:
        cbin[c] += 1

    ssum = 0
    for i in range(k):
        ssum += cbin[i]
        cbin[i] = ssum

    count = [0] * k
    for i in reversed(lmss):
        c = s[i]
        sa[cbin[c]-1 - count[c]] = i
        count[c] += 1

    count = [0] * k
    for i in sa:
        if i <= 0 or t[i-1]:
            continue
        c = s[i-1]
        sa[cbin[c-1] + count[c]] = i-1
        count[c] += 1
        
    count = [0] * k
    for i in reversed(sa):
        if i <= 0 or not t[i-1]:
            continue
        c = s[i-1]
        sa[cbin[c]-1 - count[c]] = i-1
        count[c] += 1

    return sa


def sa_is(s, k):
    slen = len(s)
    t = [True] * slen # S -> True, T -> False
    for i in range(slen-2, -1, -1):
        #if s[i] < s[i+1]:   t[i] = True #'S'
        if s[i] > s[i+1]:
            t[i] = False # 'L'
        elif s[i] == s[i+1]:
            t[i] = t[i+1]

    lmss = []
    for i in range(1,slen):
        if not t[i-1] and t[i]: # lms(t, i):
            lmss.append(i)

    seed = lmss

    sa = induced_sort(s, k, t, seed)

    new_sa = []
    for i in sa:
        if lms(t, i): new_sa.append(i)

    nums = dict() #    nums = [[]] * (max(new_sa)+1)
    nums[new_sa[0]] = 0
    num = 0
    for o in range(len(new_sa)-1):
        i, j = new_sa[o], new_sa[o+1]
        diff, d = False, 0
        for d in range(slen):
            if s[i+d] != s[j+d] or lms(t, i+d) != lms(t, j+d):
                diff = True
                break
            elif d > 0 and (lms(t, i+d) or lms(t, j+d)):
                break
        if diff:
            num += 1
        nums[j] = num

#    for i in range(len(nums)-1,-1,-1):
#        if not nums[i]: nums.pop(i)
    nums = list(map(lambda x: x[1], sorted(nums.items())))

    if num + 1 < len(nums):
        sa = sa_is(nums, num+1)
    else:
        sa = [[]] * (max(nums)+1)
        for i, c in enumerate(nums):
            sa[c] = i

    seed = list(map(lambda x:lmss[x], sa))
    sa = induced_sort(s, k, t, seed)

    return sa


def strcmp(a, b):
    for i, bi in enumerate(b):
        if a[i] == bi: continue
        return a[i]-bi
    return 0


def search(s, sa, slen, q):
    ss = 0
    ee = slen
    while ss <= ee:
        mid = (ss+ee)//2
        if mid >= slen: break
        rr = strcmp(s[sa[mid]:], q)
        if rr==0: return 1
        if rr >= 0:
            ee = mid-1
        else:
            ss = mid+1
    return 0


if __name__ == '__main__':

    b = sys.stdin.readline().rstrip()
    b = (b+'$').encode()
    sa = sa_is(b, 128) #ord('z'))
    n = int(sys.stdin.readline())
    for _ in range(n):
        q = sys.stdin.readline().rstrip().encode()
        if search(b, sa, len(b), q) > 0:
            print(1)
        else:
            print(0)

Submission status: Accepted

Solution code:
from collections import Counter
import time

def SL(S):
    t = ["S"]*len(S)
    for i in range(len(S)-2,-1,-1):
        if S[i] > S[i+1] or (S[i] == S[i+1] and t[i+1] == "L"):
            t[i] = "L"
    return t

def LMS(t):
    lms = [False]*len(t)
    for i in range(1,len(t)):
        if t[i-1] == "L" and t[i] == "S":
            lms[i] = True
    return lms

def Bucket(S):
    bucket = Counter(S)
    tmp = 0
    for i in sorted(bucket):
        bucket[i] = {"chead":tmp,"ctail":tmp+bucket[i]-1}
        tmp = bucket[i]["ctail"]+1
    return bucket

def STEP2(S,t,bucket,SA):
    for i in range(len(SA)):
        tmp = SA[i]-1
        if t[tmp] == "L" and tmp > -1:
            head = bucket[S[tmp]]["chead"]
            SA[head] = tmp
            bucket[S[tmp]]["chead"]+=1

def STEP3(S,t,SA):
    bucket = Bucket(S)
    for i in range(len(SA)-1,-1,-1):
        tmp = SA[i]-1
        if t[tmp] == "S" and tmp > -1:
            tail = bucket[S[tmp]]["ctail"]
            SA[tail] = tmp
            bucket[S[tmp]]["ctail"]-=1
        
def InducedSorting(S):
    l = len(S)
    t = SL(S)
    lms = LMS(t)
    bucket = Bucket(S)
    SA=[-1]*l
    P1 = [i for i in range(l) if lms[i]]
    #STEP1
    for i,j in enumerate(lms):
        if j:
            tail = bucket[S[i]]["ctail"]
            SA[tail] = i
            bucket[S[i]]["ctail"] -= 1
    #STEP2
    STEP2(S,t,bucket,SA)
    #STEP3
    STEP3(S,t,SA)
    #Construct S1 from pseudoSA
    prev = None
    Name = [None]*l
    name = 0
    S1 = []
    for i in SA:
        if lms[i]:
            if prev and not i == len(S)-1:
                j = 0
                while(True):
                    if not S[i+j] == S[prev+j] or not t[i+j] == t[prev+j]:
                        name+=1
                        break
                    if j>0 and lms[i+j]:
                        break
                    j+=1
            Name[i] = name
            prev = i
    for i in Name:
        if not i == None:
            S1.append(i)
    #Construct SA1 from S1
    uniq = True
    dtmp = {}
    #for i in Counter(S1):
    #    if Counter(S1)[i] > 1:
    #        uniq = False
    #        break
    for i in S1:
        if i in dtmp:
            uniq = False
            break
        else:
            dtmp[i] = True
    
    if uniq:
        SA1 = [None]*len(S1)
        for i,j in enumerate(S1):
            SA1[j] = i
    else:
        SA1 = InducedSorting(S1)
    
    #Inducing SA from SA1 STEP1
    bucket = Bucket(S)
    SA=[-1]*l
    for i in SA1[::-1]:
        p = P1[i]
        tail = bucket[S[p]]["ctail"]
        SA[tail] = p
        bucket[S[p]]["ctail"] -= 1
    #Inducing SA from SA1 STEP2
    STEP2(S,t,bucket,SA)
    #Inducing SA from SA1 STEP3
    STEP3(S,t,SA)
    return SA

def contain(T,sa,P):
    a = 0
    b = len(T)
    while(b-a > 1):
        c = (a+b)//2
        if T[sa[c]:sa[c]+len(P)] < P:
            a = c
        else:
            b = c
    return P == T[sa[b]:sa[b]+len(P)]

T = input()
Q = int(input())
P = [input() for _ in range(Q)]
SA = InducedSorting(T+"$")
for i in P:
    if contain(T,SA,i):
        print(1)
    else:
        print(0)

Submission status: Runtime Error

Solution code:
base = 127
mask = (1 << 32) - 1


def calc_hash(f, pl, tl):
    dl = tl - pl
    tmp = set()

    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = e * base + f[i]
    for i in range(dl):
        tmp.add(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.add(e)
    return tmp


t = [ord(c) for c in input().strip()]
tl = len(t)
q = int(input())
h = dict()
while q:
    p = [ord(c) for c in input().strip()]
    pl = len(p)
    key = calc_hash(p, pl, pl).pop() & mask
    if pl in h:
        haystack = h[pl]
    else:
        haystack = calc_hash(t, pl, tl)
        h[pl] = haystack
    print(1 if key in haystack else 0)

Submission status: Runtime Error

Solution code:
base = 127
mask = (1 << 32) - 1


def calc_hash(f, pl, tl):
    dl = tl - pl
    tmp = set()

    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = e * base + f[i]
    for i in range(dl):
        tmp.add(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.add(e)
    return tmp


t = [ord(c) for c in input().strip()]
tl = len(t)
q = int(input())
h = dict()
while q:
    p = [ord(c) for c in input().strip()]
    pl = len(p)
    key = calc_hash(p, pl, pl).pop() & mask
    if pl in h:
        haystack = h[pl]
    else:
        haystack = calc_hash(t, pl, tl)
        h[pl] = haystack
    print(1 if key in haystack else 0)
    q -= 1

Submission status: Runtime Error

Solution code:
base = 127
mask = (1 << 32) - 1


def calc_hash(f, pl, tl, with_array):
    dl = tl - pl
    tmp = []

    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + f[i]) & mask
    for i in range(dl):
        tmp.append(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.append(e)
    if with_array:
        return set(tmp), tmp
    else:
        return set(tmp)


t = [ord(c) for c in input().strip()]
tl = len(t)
q = int(input())
h = dict()
while q:
    p = [ord(c) for c in input().strip()]
    pl = len(p)
    if pl > tl:
        print(0)
        q -= 1
        continue
    if pl >= 10:
        keys_set, keys_array = calc_hash(p, 10, pl, with_array=True)
        keys0, keys1 = keys_array[0], keys_array[1:pl - 9]
        if pl not in h:
            hash_set, hash_array = h[10] = calc_hash(t, 10, tl, with_array=True)
        else:
            hash_set, hash_array = h[10]

        if keys_set.issubset(hash_set):
            for idx, hash in enumerate(hash_array):
                if keys0 == hash and hash_array[idx + 1:idx + pl - 9] == keys1:
                    print(1)
                    break
            else:
                print(0)
        else:
            print(0)
    else:
        key = calc_hash(p, pl, pl).pop() & mask
        if pl not in h:
            h[pl] = calc_hash(t, pl, tl, with_array=False)
        print(1 if key in h[pl] else 0)
    q -= 1

Submission status: Runtime Error

Solution code:
#coding:utf-8

def MSM(T,P):
    Tlist=list(T)
    Plist=list(P)
    ans=0
    for i in range(len(Tlist)):
        if Tlist[i]==Plist[0]:
            ans+=1
            for j in range(1,len(Plist)):
                if Plist[j]==Tlist[i+j] and i+j<=len(Tlist):
                    ans+=1
        if ans==len(Plist):
            return 1
    return 0

if __name__=="__main__":
    T=input()
    n=int(input())
    ans=[]
    for i in range(n):
        P=input()
        ans.append(MSM(T,P))
    for i in range(n):
        print(ans[i])

Submission status: Runtime Error

Solution code:
T = input()
n = int(input())
P = input()

for a in range(n):
    for i in range(len(T)-len(P)+1):
        if T[i:i+len(P)] == P:
            print(1)
            return
        else:
            print(0)
            return:

Submission status: Runtime Error

Solution code:
T = input()
n = int(input())
P = input()

for a in range(n):
    for i in range(len(T)-len(P)+1):
        if T[i:i+len(P)] == P:
            print(1)
            return
        else:
            print(0)
            return

Submission status: Runtime Error

Solution code:
x = input()
n = int(input())


def check(string,word):
    search_state = 0
    l = len(string)
    i = 0
    while (i < l):
        # print(string[i])
        if string[i+search_state] == word[search_state]:
            search_state += 1
            if search_state == len(word):
                return 1
        else:
            i += max(search_state,1)
            search_state = 0
            
    return 0
            
# print(check(x,'baa'))
    
for i in range(n):
    y = input()
    print(check(x,y))

Submission status: Runtime Error

Solution code:
from collections import defaultdict


class IndexMatch:
    shift = 40
    size = 33554393

    def __init__(self, text):
        self.text = text
        self.index = self._create_index()

    def _create_index(self):
        index = defaultdict(list)
        index[self.text[0]].append(0)

        for i in range(1, len(self.text)):
            index[self.text[i-1:i+1]].append(i-1)
            index[self.text[i]].append(i)

        return index

    def match(self, search_text):
        def _match(text):
            ls = len(text)
            if ls <= 2:
                return [(i, i+ls-1) for i in self.index[text]]

            mid = ls // 2
            pre = _match(text[:mid])
            post = _match(text[mid:])

            if len(pre) == 0 or len(post) == 0:
                return []

            indices = []
            for (s1, e1) in pre:
                (s2, e2) = self._find(post, e1+1)
                if s2 > 0:
                    indices.append(s1, e2)

            return indices

        return len(_match(search_text)) > 0

    def _find(self, ts, i):
        if len(ts) == 0:
            return (-1, -1)
        mid = len(ts) // 2
        s, e = ts[mid]
        if s > i:
            return self._find(ts[mid+1:], i)
        elif s < i:
            return self._find(ts[:mid], i)
        else:
            return (s, e)


def run():
    s1 = input()
    n = int(input())

    matcher = IndexMatch(s1)
    for _ in range(n):
        s2 = input()
        if matcher.match(s2):
            print(1)
        else:
            print(0)


if __name__ == '__main__':
    run()

Submission status: Runtime Error

Solution code:
from collections import defaultdict, Counter
from math import floor, log


class NoMatch(Exception):
    pass


class IndexMatch:
    MAX_KEYLEN = 20

    def __init__(self, text):
        self.text = text
        self.keylen = self._select_keylen()
        self._create_index()

    def _select_keylen(self):
        chars = Counter(list(self.text))
        return min(floor(log(len(self.text), len(chars))), self.MAX_KEYLEN)

    def _create_index(self):
        index = defaultdict(set)
        particles = set()
        for i in range(len(self.text)+1):
            for j in range(max(i-self.keylen, 0), i):
                if i - j < self.keylen // 2:
                    particles.add(self.text[j:i])
                else:
                    index[self.text[j:i]].add(j)
        self.index = index
        self.particles = particles

    def match(self, search_text):
        def _match(lo, hi):
            text = search_text[lo:hi]
            if hi-lo <= self.keylen:
                return self.index[text]

            mid = (lo + hi) // 2
            pre = _match(lo, mid)
            post = _match(mid, hi)

            if len(pre) == 0 or len(post) == 0:
                raise NoMatch()

            indices = set(i for i in pre if i+mid-lo in post)
            return indices

        if len(search_text) < self.keylen // 2:
            return search_text in self.particles

        try:
            match = _match(0, len(search_text))
            return len(match) > 0
        except NoMatch:
            return False


def run():
    s1 = input()
    n = int(input())
    ss = []

    for _ in range(n):
        ss.append(input())

    i = 0
    maxsize = 100000
    results = [False] * n
    while i < n:
        matcher = IndexMatch(s1[i:i+maxsize])
        for j, s2 in enumerate(ss):
            if not results[j]:
                results[j] = matcher.match(s2)

        i = i + maxsize - 1000

    for result in results:
        if result:
            print(1)
        else:
            print(0)


if __name__ == '__main__':
    run()