Buggy python submission (verdict: Time Limit Exceeded):
def search(s1, s2):
    len1 = len(s1)
    len2 = len(s2)
    for i in range(len1):
        if i + len2 > len1:
            break

        for j in range(len2):
            if s1[i+j] != s2[j]:
                break
        else:
            yield i


def run():
    s1 = input()
    s2 = input()
    for idx in search(s1, s2):
        print(idx)


if __name__ == '__main__':
    run()



Fixed submission:
class RKSearch:
    shift = 40
    size = 33554393

    def __init__(self, s1, s2):
        self.haystack = self._encode(s1)
        self.needle = self._encode(s2)

    def find(self):
        m, n = len(self.haystack), len(self.needle)
        if m < n:
            return

        h1 = self._hash(self.haystack, n)
        h2 = self._hash(self.needle, n)
        dm = self.shift**(n-1) % self.size

        for i in range(m-n+1):
            if h1 == h2:
                yield i
            if i+n < m:
                h1 = ((h1 - self.haystack[i]*dm) * self.shift
                      + self.haystack[i+n]) % self.size

    def _hash(self, s, length):
        h = 0
        for i in range(length):
            h = (h * self.shift + s[i]) % self.size

        return h

    def _encode(cls, s):
        basea = int.from_bytes(b'a', 'little')
        based = int.from_bytes(b'0', 'little')
        bs = []
        for c in s:
            if c.isdigit():
                bs.append(int.from_bytes(c.encode('utf8'), 'little')-based+27)
            else:
                bs.append(int.from_bytes(c.encode('utf8'), 'little')-basea)

        return bs


def run():
    s1 = input()
    s2 = input()
    rk = RKSearch(s1, s2)
    for i in rk.find():
        print(i)


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
def search_by_find(s1, s2):
    idx = s1.find(s2)
    while idx >= 0:
        yield idx 
        idx = s1.find(s2, idx+1)

def run():
    s1 = input()
    s2 = input()
    for idx in search_by_find(s1, s2):
        print(idx)


if __name__ == '__main__':
    run()



Fixed submission:
class RKSearch:
    shift = 40
    size = 33554393

    def __init__(self, s1, s2):
        self.haystack = self._encode(s1)
        self.needle = self._encode(s2)

    def find(self):
        m, n = len(self.haystack), len(self.needle)
        if m < n:
            return

        h1 = self._hash(self.haystack, n)
        h2 = self._hash(self.needle, n)
        dm = self.shift**(n-1) % self.size

        for i in range(m-n+1):
            if h1 == h2:
                yield i
            if i+n < m:
                h1 = ((h1 - self.haystack[i]*dm) * self.shift
                      + self.haystack[i+n]) % self.size

    def _hash(self, s, length):
        h = 0
        for i in range(length):
            h = (h * self.shift + s[i]) % self.size

        return h

    def _encode(cls, s):
        basea = int.from_bytes(b'a', 'little')
        based = int.from_bytes(b'0', 'little')
        bs = []
        for c in s:
            if c.isdigit():
                bs.append(int.from_bytes(c.encode('utf8'), 'little')-based+27)
            else:
                bs.append(int.from_bytes(c.encode('utf8'), 'little')-basea)

        return bs


def run():
    s1 = input()
    s2 = input()
    rk = RKSearch(s1, s2)
    for i in rk.find():
        print(i)


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Runtime Error):
def search_by_dict(s1, s2):
    d = defaultdict(list)

    for i in range(len(s1)-len(s2)):
        d[s1[i:i+len(s2)]].append(i)

    return (i for i in d[s2])


def run():
    s1 = input()
    s2 = input()
    for idx in search_by_dict(s1, s2):
        print(idx)


if __name__ == '__main__':
    run()


Fixed submission:
class RKSearch:
    shift = 40
    size = 33554393

    def __init__(self, s1, s2):
        self.haystack = self._encode(s1)
        self.needle = self._encode(s2)

    def find(self):
        m, n = len(self.haystack), len(self.needle)
        if m < n:
            return

        h1 = self._hash(self.haystack, n)
        h2 = self._hash(self.needle, n)
        dm = self.shift**(n-1) % self.size

        for i in range(m-n+1):
            if h1 == h2:
                yield i
            if i+n < m:
                h1 = ((h1 - self.haystack[i]*dm) * self.shift
                      + self.haystack[i+n]) % self.size

    def _hash(self, s, length):
        h = 0
        for i in range(length):
            h = (h * self.shift + s[i]) % self.size

        return h

    def _encode(cls, s):
        basea = int.from_bytes(b'a', 'little')
        based = int.from_bytes(b'0', 'little')
        bs = []
        for c in s:
            if c.isdigit():
                bs.append(int.from_bytes(c.encode('utf8'), 'little')-based+27)
            else:
                bs.append(int.from_bytes(c.encode('utf8'), 'little')-basea)

        return bs


def run():
    s1 = input()
    s2 = input()
    rk = RKSearch(s1, s2)
    for i in rk.find():
        print(i)


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Time Limit Exceeded):
def search_by_hash(s1, s2):
    tg = hash(bytes(s2, 'utf8'))
    sb = memoryview(bytes(s1, 'utf8'))
    l1, l2 = len(s1), len(s2)

    for i in range(l1-l2+1):
        h = hash(sb[i:i+l2])
        if h == tg:
            yield i

def run():
    s1 = input()
    s2 = input()
    for idx in search_by_hash(s1, s2):
        print(idx)


if __name__ == '__main__':
    run()


Fixed submission:
class RKSearch:
    shift = 40
    size = 33554393

    def __init__(self, s1, s2):
        self.haystack = self._encode(s1)
        self.needle = self._encode(s2)

    def find(self):
        m, n = len(self.haystack), len(self.needle)
        if m < n:
            return

        h1 = self._hash(self.haystack, n)
        h2 = self._hash(self.needle, n)
        dm = self.shift**(n-1) % self.size

        for i in range(m-n+1):
            if h1 == h2:
                yield i
            if i+n < m:
                h1 = ((h1 - self.haystack[i]*dm) * self.shift
                      + self.haystack[i+n]) % self.size

    def _hash(self, s, length):
        h = 0
        for i in range(length):
            h = (h * self.shift + s[i]) % self.size

        return h

    def _encode(cls, s):
        basea = int.from_bytes(b'a', 'little')
        based = int.from_bytes(b'0', 'little')
        bs = []
        for c in s:
            if c.isdigit():
                bs.append(int.from_bytes(c.encode('utf8'), 'little')-based+27)
            else:
                bs.append(int.from_bytes(c.encode('utf8'), 'little')-basea)

        return bs


def run():
    s1 = input()
    s2 = input()
    rk = RKSearch(s1, s2)
    for i in rk.find():
        print(i)


if __name__ == '__main__':
    run()

Buggy python submission (verdict: Runtime Error):

class RKSearch:
    shift = 40
    size = 33554393

    def __init__(self, s1, s2):
        self.haystack = self.encode(s1)
        self.needle = self.encode(s2)

    def find(self):
        m, n = len(self.haystack), len(self.needle)
        h1 = self.hash(self.haystack, n)
        h2 = self.hash(self.needle, n)
        dm = self.shift**(n-1) % self.size

        for i in range(m-n+1):
            if h1 == h2:
                yield i
            if i+n < m:
                h1 = ((h1 - self.haystack[i]*dm) * self.shift
                      + self.haystack[i+n]) % self.size

    def hash(self, s, length):
        h = 0
        for i in range(length):
            h = (h * self.shift + s[i]) % self.size

        return h

    def encode(cls, s):
        basea = int.from_bytes(b'a', 'little')
        based = int.from_bytes(b'0', 'little')
        bs = []
        for c in s:
            if c.isdigit():
                bs.append(int.from_bytes(c.encode('utf8'), 'little')-based+27)
            else:
                bs.append(int.from_bytes(c.encode('utf8'), 'little')-basea)

        return bs


def run():
    s1 = input()
    s2 = input()
    rk = RKSearch(s1, s2)
    for i in rk.find():
        print(i)


if __name__ == '__main__':
    run()



Fixed submission:
class RKSearch:
    shift = 40
    size = 33554393

    def __init__(self, s1, s2):
        self.haystack = self._encode(s1)
        self.needle = self._encode(s2)

    def find(self):
        m, n = len(self.haystack), len(self.needle)
        if m < n:
            return

        h1 = self._hash(self.haystack, n)
        h2 = self._hash(self.needle, n)
        dm = self.shift**(n-1) % self.size

        for i in range(m-n+1):
            if h1 == h2:
                yield i
            if i+n < m:
                h1 = ((h1 - self.haystack[i]*dm) * self.shift
                      + self.haystack[i+n]) % self.size

    def _hash(self, s, length):
        h = 0
        for i in range(length):
            h = (h * self.shift + s[i]) % self.size

        return h

    def _encode(cls, s):
        basea = int.from_bytes(b'a', 'little')
        based = int.from_bytes(b'0', 'little')
        bs = []
        for c in s:
            if c.isdigit():
                bs.append(int.from_bytes(c.encode('utf8'), 'little')-based+27)
            else:
                bs.append(int.from_bytes(c.encode('utf8'), 'little')-basea)

        return bs


def run():
    s1 = input()
    s2 = input()
    rk = RKSearch(s1, s2)
    for i in rk.find():
        print(i)


if __name__ == '__main__':
    run()