output_description: For each question, print 1 if the text includes P_i, or print 0 otherwise.
input_description: 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.
attempt: 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()
  
problem_description: String Search
  
  Determine whether a text T includes a pattern P. Your program should answer
  for given queries consisting of P_i.
samples: [{"input": "aabaaa\n    4\n    aa\n    ba\n    bb\n    xyz", "output": "1\n    1\n    0\n    0"}]