Problem:


String Search

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

Input

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

Output

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

Constraints

  
 1 ≤ length of T ≤ 1000000 

  
 1 ≤ length of P_i ≤ 1000 

  
 1 ≤ Q ≤ 10000 

  
The input consists of alphabetical characters and digits

Sample Input 1

aabaaa
4
aa
ba
bb
xyz

Sample Output 1

1
1
0
0



Sample input:
aabaaa
4
aa
ba
bb
xyz


Sample output:
1
1
0
0

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

def searchPatterns(origin_string, length):
    patterns = []
    for index in range(0, len(origin_string)-(length-1)):
        patterns.append(original_string[index:index+length])
    return patterns

original_string = input()
original_patterns = [None for i in range(len(original_string))]
check_string_count = int(input())
checkers = [input() for i in range(check_string_count)]
for checker in checkers:
    if len(checker) > len(original_string):
        print(0)
        continue
    if original_patterns[len(checker)] == None:
        original_patterns[len(checker)] = searchPatterns(original_patterns, len(checker))
    print(1 if checker in original_patterns[len(checker)] else 0)

Submission status: Time Limit Exceeded

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


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

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


t = [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(20, pl)
    keys = calc_hash(p, bs, pl)
    if bs not in h:
        h[bs] = calc_hash(t, bs, tl)
    a.append(1 if keys.issubset(h[bs]) else 0)
print('\n'.join(map(str, a)))

Submission status: Time Limit Exceeded

Solution code:

def BitapSearch(Text,Pattern):
    
    T_MAX = 1000000
    P_MAX = 1000
    R = ~1

    pattern_mask = [ ~0 for _ in range(T_MAX)]
    
    for i in range(len(Pattern)):
        pattern_mask[ord(Pattern[i])] &= ~(1 << i)
    
    for i in range(len(Text)):
        R = R|pattern_mask[ord(Text[i])]
        R = R << 1
        if R & (1 << len(Pattern)) == 0:
            return True
    
    return False

Text = input()
n = int(input())

for _ in range(n):
    Pattern = input()

    if BitapSearch(Text,Pattern):
        print(1)
    else:
        print(0)

Submission status: Time Limit Exceeded

Solution code:
t = input()
q = int(input())

for i in range(q):
    p = input()
    if p in t:
        print(1)
    else:
        print(0)

Submission status: Time Limit Exceeded

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

for i in range(n):
    y = input()
    if y in x:
        print(1)
    else:
        print(0)

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

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


def check(string,word):
    search_state = 0
    first_match = 0
    l = len(string)
    i = 0
    while (i < l):
        if i+len(word) > l:
            break
        if word[0] != string[i] or word[-1] != string[i+len(word)-1]:
            i += 1
            continue
        # print(string[i])
        if string[i+search_state] == word[search_state]:
            if first_match == 0:
                first_match = search_state
            search_state += 1
            if search_state == len(word):
                return 1
        else:
            i += max(min(first_match,search_state),1)
            search_state = 0
            
    return 0
            
# print(check(x,'baa'))
    
for i in range(n):
    y = input()
    print(check(x,y))
    
# for i in range(n):
#     y = input()
#     print(str(i) + y)
#     # if y in x:
    #     print(i + 1)
    # else:
    #     print(i + 0)

Submission status: Time Limit Exceeded

Solution code:
def MAIN():
    T = input()
    Q = int(input())
    P = ""
    for _ in range(Q):
        P = input()
        print(1 if P in T else 0)
MAIN()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import OrderedDict


def main():
    inputStr = sys.stdin.read()
    lines = inputStr.split("\n")
    text, words = lines[0], lines[2:-1]
    words_by_length = {}
    for i, word in enumerate(words):
        if len(word) in words_by_length:
            words_by_length[len(word)].append((i, word))
        else:
            words_by_length[len(word)] = [(i, word)]
    words_by_length = OrderedDict(sorted(words_by_length.items(), key=lambda t: t[0]))
    found_indices = set([])
    text_length = len(text)
    for i in range(text_length):
        for word_length, words_by_index in words_by_length.items():
            if i + word_length > text_length:
                break
            sliced = text[i:(i + word_length)]
            founds = []
            for j, (index, word) in enumerate(words_by_index):
                if sliced == word:
                    found_indices.add(index)
                    founds.insert(0, j)
            for j in founds:
                words_by_index.pop(j)

    for i in range(len(words)):
        if i in found_indices:
            print(1)
        else:
            print(0)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
T=input()
for _ in[0]*int(input()):print((input()in T)*1)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict


class IndexMatch:
    shift = 40
    size = 33554393

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

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

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

        return index

    def match(self, search_text):
        def _match(text):
            ls = len(text)
            if ls <= 2:
                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()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Memory Limit Exceeded

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


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

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


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

Submission status: Memory Limit Exceeded

Solution code:
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.index = self._create_index()
        # print(self.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)
        for i in range(len(self.text)+1):
            for j in range(max(i-self.keylen, 0), i):
                index[self.text[j:i]].add(j)
        return index

    def match(self, search_text):
        def _match(lo, hi):
            text = search_text[lo:hi]
            if hi-lo <= self.keylen or text in self.index:
                # print(text, self.index[text])
                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)
            self.index[text] = indices
            # print(text, hi, lo, mid, len(pre), len(post), len(indices))
            return indices

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

Submission status: Memory Limit Exceeded

Solution code:
from collections import defaultdict, 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, 15)

    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

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

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


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

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


if __name__ == '__main__':
    run()

Submission status: Accepted

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


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

Submission status: Accepted

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


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

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


t = [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)))

Submission status: Accepted

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


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

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


t = [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)))

Submission status: Accepted

Solution code:
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)))