Buggy python submission (verdict: Runtime Error):
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()



Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
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:
                indices = [(i, i+ls-1) for i in self.index[text]]
                return indices

            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], i)
        elif s < i:
            return self._find(ts[mid+1:], 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()



Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from math import ceil, log


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

    def _select_keylen(self):
        chars = set(list(self.text))
        return ceil(log(len(self.text), len(chars)))

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

        for i in range(1, len(self.text)):
            c = self.text[i]
            index[c].append(i)
            st2 = [c]
            while len(st1) > 0:
                s = st1.pop() + c
                index[s].append(i-len(s)+1)
                if len(s) <= self.keylen:
                    st2.append(s)
            st1, st2 = st2, st1

        return index

    def match(self, search_text):
        def _match(text):
            ls = len(text)
            if ls <= 2 or text in self.index:
                return self.index[text]

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

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

            indices = [i for i in pre if (i+mid) in post]
            self.index[text] = indices
            return indices

        return len(_match(search_text)) > 0


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



Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from math import floor, log 


class NoMatch(Exception):
    pass


class IndexMatch:

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

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

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

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


if __name__ == '__main__':
    run()



Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from math import floor, log 


class NoMatch(Exception):
    pass


class IndexMatch:
    MAX_KEYLEN = 15

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

    def _select_keylen(self):
        chars = set(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())

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


if __name__ == '__main__':
    run()



Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from math import floor, log 


class NoMatch(Exception):
    pass


class IndexMatch:
    MAX_KEYLEN = 13

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

    def _select_keylen(self):
        chars = set(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())

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


if __name__ == '__main__':
    run()



Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from math import floor, log 


class NoMatch(Exception):
    pass


class IndexMatch:
    MAX_KEYLEN = 10

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

    def _select_keylen(self):
        chars = set(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())

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


if __name__ == '__main__':
    run()



Fixed submission:
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()

Buggy python submission (verdict: Runtime Error):
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()



Fixed submission:
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()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
from math import floor, log


class NoMatch(Exception):
    pass


class HashIndex:
    MAX_KEYLEN = 15
    MAX_SEARCH = 1000

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

    def _select_keylen(self):
        chars = len(set(list(self.text)))
        textlen = len(self.text)
        if chars > 1:
            return min(floor(log(textlen, chars)), self.MAX_KEYLEN)
        else:
            return self.MAX_SEARCH+1

    def _create_index(self):
        index = defaultdict(set)
        particles = set()
        if self.keylen == self.MAX_SEARCH+1:
            for i in range(self.keylen+1):
                particles.add(self.text[0:i+1])
        else:
            for i in range(len(self.text)+1):
                for j in range(max(i-self.keylen, 0), i):
                    if i - j < self.keylen:
                        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):
            length = hi - lo
            if length == self.keylen:
                return self.index[search_text[lo:hi]]

            if length < self.keylen*2:
                results = set()
                pre = search_text[lo:lo+self.keylen]
                post = search_text[lo+self.keylen:hi]
                if post in self.particles:
                    for i in self.index[pre]:
                        if post == self.text[i+self.keylen:i+(hi-lo)]:
                            results.add(i)
                return results

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

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

            return _merge(pre, post, mid-lo)

        def _merge(idx1, idx2, shift):
            return set(i for i in idx1 if i + shift in idx2)

        length = len(search_text)
        if length < self.keylen:
            # print('check_size', search_text)
            return search_text in self.particles

        # 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)
            return len(match) > 0
        except:
            return False

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

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


if __name__ == '__main__':
    run()



Fixed submission:
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()