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

Solution (Python):
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 = [ord(c) for c in input().strip()]
tl = len(t)
q = int(input())
ps = [input().strip() for _ in range(q)]
h = dict()
c = dict()
a = []
for p in ps:
    if p in c:
        a.append(c[p])
        continue
    p = [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)))

Solution (Python):
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 = [ord(c) for c in input().strip()]
tl = len(t)
q = int(input())
ps = [input().strip() for _ in range(q)]
h = dict()
a = []
hash_len = 20
for p in ps:
    p = [ord(c) for c in p]
    pl = len(p)
    if pl > tl:
        a.append(0)
        continue
    bs = min(hash_len, 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)))

Solution (Python):
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 = [ord(c) for c in input().strip()]
tl = len(t)
q = int(input())
ps = [input().strip() for _ in range(q)]
h = dict()
a = []
hash_len = 19
for p in ps:
    p = [ord(c) for c in p]
    pl = len(p)
    if pl > tl:
        a.append(0)
        continue
    bs = min(hash_len, 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)))

Solution (Python):
import sys
readline = sys.stdin.readline
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 = readline().strip()
    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)))

Solution (Python):
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)))

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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)
        

    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
        
        

    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.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:
                
                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:
                    
                    yield i1

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

        
        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()

Solution (Python):
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

        
        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()

Solution (Python):
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)

    a.append(1 if keys.issubset(h[bs]) else 0) 
    dic[pp] = a[-1]
print('\n'.join(map(str, a)))

Solution (Python):
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  
    mask = (1 << 32) - 1  

    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)  
        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)

Solution (Python):


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 
    for i in range(slen-2, -1, -1):
        
        if s[i] > s[i+1]:
            t[i] = False 
        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]: 
            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[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



    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) 
    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)

Solution (Python):
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]]
    
    for i,j in enumerate(lms):
        if j:
            tail = bucket[S[i]]["ctail"]
            SA[tail] = i
            bucket[S[i]]["ctail"] -= 1
    
    STEP2(S,t,bucket,SA)
    
    STEP3(S,t,SA)
    
    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)
    
    uniq = True
    dtmp = {}
    
    
    
    
    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)
    
    
    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
    
    STEP2(S,t,bucket,SA)
    
    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)