Given two strings, one is a text string and other is a pattern string. The task is to print the indexes of all the occurences of pattern string in the text string. For printing, Starting Index of a string should be taken as 1.
Example 1:
Input:
S = "batmanandrobinarebat", pat = "bat"
Output: 1 18
Explanation: The string "bat" occurs twice
in S, one starts are index 1 and the other
at index 18. 
Ã¢â¬â¹Example 2:
Input: 
S = "abesdu", pat = "edu"
Output: -1
Explanation: There's not substring "edu"
present in S.
Your Task:
You don't need to read input or print anything. Your task is to complete the function search() which takes the string S and the string pat as inputs and returns an array denoting the start indices (1-based) of substring pat in the string S. 
Expected Time Complexity: O(|S|*|pat|).
Expected Auxiliary Space: O(1).
Constraints:
1<=|S|<=10^{5}
1<=|pat|<|S|

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|S|*|pat|).
Expected Auxiliary Space: O(1).

Starter code:
#User function Template for python3

class Solution:
    def search(self, patt, s):
        # code here

Solutions:
class Solution:

	def search(self, patt, S):
		arr = []
		d = 256
		q = 1000000007
		p = t = 0
		M = len(patt)
		N = len(S)
		h = d ** (M - 1) % q
		j = 0
		for i in range(M):
			p = (p * d + ord(patt[i])) % q
			t = (t * d + ord(S[i])) % q
		for i in range(N - M + 1):
			if p == t:
				while j < M:
					if S[i + j] != patt[j]:
						break
					else:
						j += 1
				if j == M:
					arr.append(i + 1)
			if i < N - M:
				t = (d * (t - ord(S[i]) * h) + ord(S[i + M])) % q
		if not len(arr):
			return [-1]
		return arr


class Solution:

	def search(self, patt, s):
		res = []
		a = len(s)
		b = len(patt)
		i = 0
		j = a - (b - 1)
		while i <= j:
			if s[i:i + b] == patt:
				res.append(i + 1)
			i += 1
		return res if len(res) > 0 else [-1]


class Solution:

	def search(self, pat, S):
		ans = []
		n = len(pat)
		i = 0
		while i < len(S) - n + 1:
			if S[i] == pat[0]:
				if S[i:i + n] == pat:
					ans.append(i + 1)
			i += 1
		if len(ans) == 0:
			ans.append(-1)
		return ans


class Solution:

	def search(self, p, s):
		m = []
		if p not in s:
			m.append(-1)
			return m
		else:
			s1 = []
			for i in range(len(s)):
				if s[i] == p[0] and s[i:i + len(p)] == p:
					s1.append(str(i + 1))
			return s1


class Solution:

	def search(self, p, s):
		res = []
		k = s[:len(p)]
		for i in range(len(s) - len(p)):
			if k == p:
				res += [i + 1]
			k = k[1:] + s[i + len(p)]
		if k == p:
			res += [len(s) - len(p) + 1]
		if len(res) > 0:
			return res
		else:
			return [-1]


class Solution:

	def search(self, patt, s):
		a = patt[0]
		b = len(patt)
		i = 0
		cnt = 0
		l = []
		while i < len(s):
			if s[i] == a:
				if s[i:i + b] == patt:
					l += [i + 1]
			i += 1
		if l:
			return l
		else:
			return [-1]


class Solution:

	def search(self, patt, s):
		i = 0
		j = 0
		c = []
		d = len(patt)
		for i in range(len(s) - len(patt) + 1):
			l = s[i:i + d]
			if l == patt:
				c.append(i + 1)
		if c == []:
			c.append(-1)
			return c
		return c


class Solution:

	def search(self, pattern, text):

		def create_partial_match_table(pattern):
			n = len(pattern)
			partial_match_table = [0] * n
			j = 0
			for i in range(1, n):
				while j > 0 and pattern[i] != pattern[j]:
					j = partial_match_table[j - 1]
				if pattern[i] == pattern[j]:
					j += 1
				partial_match_table[i] = j
			return partial_match_table
		n = len(text)
		m = len(pattern)
		partial_match_table = create_partial_match_table(pattern)
		i = j = 0
		a = []
		while i < n:
			if text[i] == pattern[j]:
				i += 1
				j += 1
				if j == m:
					a.append(i - j + 1)
					j = partial_match_table[j - 1]
			elif j > 0:
				j = partial_match_table[j - 1]
			else:
				i += 1
		if a != []:
			return a
		return [-1]


class Solution:

	def search(self, patt, s):
		if patt not in s:
			return [-1]
		else:
			k = []
			for i in range(len(s) - len(patt) + 1):
				if s[i:i + len(patt)] == patt:
					k.append(i + 1)
			return k


class Solution:

	def search(self, patt, s):
		l = []
		st = 0
		end = 0
		k = 0
		n = len(s)
		p = len(patt)
		while st < n and end < n:
			if patt[k] == s[st]:
				while k < p and end < n and (s[end] == patt[k]):
					k += 1
					end += 1
					if k == p:
						l.append(st + 1)
						break
			k = 0
			st += 1
			end = st
		if l == []:
			return [-1]
		return l


class Solution:

	def search(self, patt, s):
		li = []
		x = s.find(patt)
		length = len(patt)
		if x == -1:
			return ['-1']
		for i in range(len(s) - length + 1):
			li.append(s[i:length])
			length = length + 1
		arr = []
		for i in range(len(li)):
			if li[i] == patt:
				arr.append(i + 1)
		return arr


class Solution:

	def search(self, patt, s):
		n = len(patt)
		l = []
		for i in range(len(s) - n + 1):
			k = s[i:i + n]
			if k == patt:
				l.append(i + 1)
		if len(l) == 0:
			return [-1]
		else:
			return l


class Solution:

	def search(self, patt, s):
		i = 0
		result = []
		while i < len(s):
			if s[i] == patt[0]:
				j = i
				k = 0
				while k < len(patt) and j < len(s):
					if s[j] != patt[k]:
						break
					k += 1
					j += 1
				if k == len(patt):
					result.append(i + 1)
			i += 1
		return result if result else [-1]


class Solution:

	def search(self, patt, s):
		ans = []
		i = 0
		n = len(patt)
		m = len(s)
		j = m - (n - 1)
		while i <= j:
			if s[i:i + n] == patt:
				ans.append(i + 1)
			i += 1
		return ans if len(ans) > 0 else [-1]


class Solution:

	def search(self, patt, s):
		a = []
		for i in range(0, len(s) - len(patt) + 1):
			if s[i:i + len(patt)] == patt:
				a.append(i + 1)
		if len(a):
			return a
		else:
			return [-1]


class Solution:

	def search(self, patt, s):
		ans = []
		p = len(patt)
		st = len(s)
		for i in range(0, st - p + 1):
			if s[i:i + p] == patt:
				ans.append(i + 1)
		if len(ans) > 0:
			return ans
		else:
			return [-1]


class Solution:

	def search(self, pat, s):
		if pat not in s:
			return [-1]
		n = len(pat) - 1
		w = s.count(pat)
		ind = s.index(pat)
		if w == 1:
			return [ind + 1]
		else:
			val = [ind + 1]
			for i in range(ind + n, len(s) - n):
				q = s[i:i + n + 1]
				if q == pat:
					val.append(i + 1)
			val = sorted(set(val))
			return list(val)


class Solution:

	def search(self, patt, s):
		mltpy = 256
		mod = 101
		p = 0
		st = 0
		h = 1
		m = len(patt)
		n = len(s)
		ans = []
		for i in range(m):
			p = (p * mltpy + ord(patt[i])) % mod
			st = (st * mltpy + ord(s[i])) % mod
			h *= mltpy
		h //= mltpy
		h %= mod
		i = 0
		while i < n - m + 1:
			if p == st:
				for j in range(m):
					if s[j + i] != patt[j]:
						break
				else:
					ans.append(i + 1)
			if i != n - m:
				st = (((st - ord(s[i]) * h) * mltpy + ord(s[i + m])) % mod + mod) % mod
			i += 1
		if ans == []:
			return [-1]
		return ans


import string

class Solution:

	def search(self, pat, s):
		ans = []
		i = 0
		n = len(pat)
		m = len(s)
		j = m - (n - 1)
		while i <= j:
			if s[i:i + n] == pat:
				ans.append(i + 1)
			i += 1
		return ans if len(ans) > 0 else [-1]


class Solution:

	def search(self, patt, s):
		n = len(s)
		m = len(patt)
		res = []
		for i in range(n):
			if s[i:i + m] == patt:
				res.append(i + 1)
		if len(res) == 0:
			return [-1]
		else:
			return res


class Solution:

	def search(self, patt, s):
		m = len(patt)
		n = len(s)
		d = 256
		q = 31
		(hash1, hash2) = (0, 0)
		h = 1
		for i in range(m - 1):
			h = h * d % q
		for i in range(m):
			hash1 = (hash1 * d + ord(patt[i])) % q
			hash2 = (hash2 * d + ord(s[i])) % q
		indices = []
		for i in range(n - m + 1):
			if hash1 == hash2:
				for j in range(m):
					if patt[j] != s[i + j]:
						break
					else:
						j += 1
				if j == m:
					indices.append(i + 1)
			if i < n - m:
				hash2 = (d * (hash2 - ord(s[i]) * h) + ord(s[i + m])) % q
				if hash2 < 0:
					hash2 += q
		return indices if indices else [-1]


class Solution:

	def search(self, patt, s):
		l = []
		i = 0
		j = len(patt)
		while j <= len(s):
			if s[i:j] == patt:
				l.append(i + 1)
			j = j + 1
			i = i + 1
		if len(l) > 0:
			return l
		return [-1]


from sys import *
from math import *
from collections import *
mod = 1000000000.0 + 7

def val(p, d, np, M, powers):
	sam = 0
	for i in range(np):
		sam = (sam + d[p[i]] * powers[np - i - 1]) % mod
	return sam

def pow_list(M, np):
	powers = [1]
	for i in range(np - 1):
		powers.append(powers[i] * M % mod)
	return powers

class Solution:

	def search(self, p, s):
		np = len(p)
		ns = len(s)
		ss = set(s)
		ps = set(p)
		if len(ps.difference(ss)):
			return [-1]
		ul = len(ss)
		d = dict(zip(ss, range(ul)))
		store = []
		M = ul
		powers = pow_list(M, np)
		p_val = val(p, d, np, M, powers)
		s_val = val(s, d, np, M, powers)
		for i in range(ns - np + 1):
			if p_val == s_val:
				store.append(i + 1)
			if i == ns - np:
				break
			s_val = (s_val - d[s[i]] * powers[np - 1] + mod) % mod
			s_val = s_val * M % mod
			s_val = (s_val + d[s[i + np]]) % mod
		if store == []:
			return [-1]
		return store


class Solution:

	def search(self, patt, s):
		arr = []
		n = len(patt)
		l = len(s)
		i = 0
		while i < l:
			st = s[i:]
			if patt in st:
				i += st.index(patt) + 1
				arr.append(i)
			else:
				break
		if arr:
			return arr
		else:
			return [-1]


class Solution:

	def search(self, patt, s):
		arr = []
		l = 0
		find = 0
		r = len(patt)
		while r <= len(s):
			s1 = s[l:r]
			if patt == s1:
				arr.append(l + 1)
				find = 1
			l += 1
			r += 1
		if find == 0:
			arr.append(-1)
		return arr


class Solution:

	def search(self, patt, s):
		(d, h, q) = (26, 1, 113)
		(p, t) = (0, 0)
		(n, m) = (len(s), len(patt))
		arr = []
		for i in range(m - 1):
			h = h * d % q
		for i in range(m):
			p = (p * d + ord(patt[i])) % q
			t = (t * d + ord(s[i])) % q
		for i in range(n - m + 1):
			if p == t:
				for j in range(m):
					if s[i + j] != patt[j]:
						break
					else:
						j += 1
				if j == m:
					arr.append(i + 1)
			if i < n - m:
				t = (d * (t - ord(s[i]) * h) + ord(s[i + m])) % q
				if t < 0:
					t += q
		if len(arr) == 0:
			arr.append(-1)
		return arr


class Solution:

	def search(self, patt, s):
		res = []
		for i in range(len(s) - (len(patt) - 1)):
			if s[i:i + len(patt)] == patt:
				res.append(i + 1)
		if res == []:
			return [-1]
		return res


class Solution:

	def search(self, patt, s):
		ans = []
		i = 0
		while i <= len(s) - len(patt):
			if s[i:i + len(patt)] == patt:
				ans.append(i + 1)
			i += 1
		if ans == []:
			return [-1]
		return ans


class Solution:

	def search(self, pat, txt):
		n = len(txt)
		m = len(pat)
		h = 1
		q = 101
		d = 256
		list1 = []
		for i in range(1, m):
			h = h * d % q
		p = 0
		t = 0
		for i in range(m):
			p = (p * d + ord(pat[i])) % q
			t = (t * d + ord(txt[i])) % q
		for i in range(n - m + 1):
			if p == t:
				flag = True
				for j in range(m):
					if txt[i + j] != pat[j]:
						flag = False
						break
				if flag == True:
					list1.append(i + 1)
			if i < n - m:
				t = (d * (t - ord(txt[i]) * h) + ord(txt[i + m])) % q
				if t < 0:
					t = t + q
		if len(list1) > 0:
			return list1
		return [-1]


class Solution:

	def search(self, patt, s):
		lp = len(patt)
		ls = len(s)
		ans = []
		for i in range(ls - lp + 1):
			match = True
			for j in range(lp):
				if s[i + j] != patt[j]:
					match = False
					break
			if match:
				ans.append(i + 1)
		if ans == []:
			return [-1]
		return ans


class Solution:

	def search(self, patt, s):
		window = len(patt)
		length = len(s)
		slides = length - window + 1
		O = []
		for i in range(slides):
			if s[i:window] == patt:
				O.append(i + 1)
			window += 1
		if O == []:
			return [-1]
		return O


class Solution:

	def search(self, pat, s):
		dic = {chr(i + 97): i for i in range(26)}
		pat_count = 0
		for elm in pat:
			pat_count += dic[elm]
		temp = ''
		count = 0
		for i in range(len(pat)):
			temp += s[i]
			count += dic[s[i]]
		i = 1
		j = len(pat)
		candidate = {}
		while j < len(s):
			if count == pat_count:
				candidate[i] = temp
			temp = s[i:j] + s[j]
			count = count - dic[s[i - 1]] + dic[s[j]]
			i += 1
			j += 1
		if count == pat_count:
			candidate[i] = temp
		res = []
		for (key, val) in candidate.items():
			if val == pat:
				res.append(key)
		if res == []:
			return [-1]
		res.sort()
		return res


class Solution:

	def search(self, patt, s):
		if patt == s:
			return 0
		d = {chr(i): i - 96 for i in range(97, 97 + 26)}
		p_val = 0
		s_val = 0
		for i in range(0, len(patt)):
			p_val += d[patt[i]]
			s_val += d[s[i]]
		i = 0
		j = len(patt) - 1
		ans = {}
		while j < len(s):
			if p_val == s_val:
				ans[i + 1] = s[i:j + 1]
			if j + 1 < len(s):
				s_val = s_val - d[s[i]] + d[s[j + 1]]
			j += 1
			i += 1
		res = []
		for i in ans:
			if ans[i] == patt:
				res.append(i)
		res.sort()
		return [-1] if len(res) == 0 else res


class Solution:

	def search(self, patt, s):
		n = len(s)
		m = len(patt)
		a = []
		for i in range(n - m + 1):
			if s[i:i + m] == patt:
				a.append(i + 1)
		if not a:
			return [-1]
		return a
Solution()


class Solution:

	def search(self, patt, s):
		ind = []
		for i in range(0, len(s)):
			x = i
			if s[i] == patt[0]:
				for j in range(0, len(patt)):
					if i >= len(s) or s[i] != patt[j]:
						break
					if j == len(patt) - 1:
						ind.append(x + 1)
					i += 1
				i = x
		if len(ind) == 0:
			ind.append(-1)
		return ind


class Solution:

	def check_match(self, s, patt):
		length = len(patt)
		for i in range(length):
			if s[i] != patt[i]:
				return False
		return True

	def search(self, patt, s):
		d = 256
		output = []
		prime = 5641
		hash_value = 0
		hash_check = 0
		power = 1
		for i in range(len(patt)):
			power = power * d % prime
		for i in range(len(patt)):
			hash_value = (hash_value * d + ord(patt[i])) % prime
		patt_len = len(patt)
		flag = 0
		for i in range(0, len(s)):
			hash_check = (hash_check * d + ord(s[i])) % prime
			if i < patt_len - 1:
				continue
			if i >= patt_len:
				hash_check = (hash_check - ord(s[i - patt_len]) * power) % prime
			if hash_check < 0:
				hash_check += prime
			if hash_value == hash_check:
				if self.check_match(s[i - patt_len + 1:], patt):
					flag = 1
					output.append(i - patt_len + 2)
		if flag == 0:
			return [-1]
		return output


class Solution:

	def search(self, patt, s):
		ans_list = []
		for i in range(len(s)):
			if s[i] == patt[0]:
				j = i
				k = 0
				while j < len(s) and k < len(patt):
					if s[j] != patt[k]:
						break
					else:
						j += 1
						k += 1
				if k == len(patt):
					ans_list.append(i + 1)
		if len(ans_list) == 0:
			ans_list.append(-1)
		return ans_list


import re

class Solution:

	def search(self, patt, s):
		l = []
		i = re.finditer(patt, s)
		ind = [index.start() for index in i]
		if set(s) == set(patt) and len(set(s)) == 1:
			for i in range(1, len(s)):
				l.append(i)
			return l
		if len(ind) == 0:
			return [-1]
		for i in ind:
			l.append(i + 1)
		return l


class Solution:

	def search(self, patt, text):
		matches = []
		start = 0
		while True:
			index = text.find(patt, start)
			if index == -1:
				break
			matches.append(index + 1)
			start = index + 1
		return matches if matches else [-1]
		return


class Solution:

	def search(self, patt, s):
		k = []
		l = [-1]
		flag = False
		for i in range(len(s)):
			if s[i:i + len(patt)] == patt:
				k.append(i + 1)
				flag = True
		if len(k) == 0:
			return l
		else:
			return k


class Solution:

	def search(self, patt, s):
		if patt not in s:
			return [-1]
		lst = []
		for i in range(0, len(s) - len(patt) + 1):
			v = s[i:i + len(patt)]
			if v == patt:
				lst.append(i + 1)
		return lst


class Solution:

	def match(self, st, patt):
		n = len(patt)
		for i in range(n):
			if st[i] != patt[i]:
				return False
		return True

	def search(self, patt, s):
		m = len(patt)
		n = len(s)
		ans = []
		hashVal = 0
		for i in patt:
			hashVal += ord(i)
		temp = 0
		for i in range(m):
			temp += ord(s[i])
		if temp == hashVal and self.match(s[:m], patt):
			ans.append(1)
		j = 0
		for i in range(m, n):
			temp += ord(s[i]) - ord(s[j])
			if temp == hashVal and self.match(s[j + 1:i + 1], patt):
				ans.append(j + 2)
			j += 1
		if ans:
			return ans
		return [-1]


class Solution:

	def search(self, pattern, text):
		n = len(text)
		m = len(pattern)
		pi = [0] * m
		j = 0
		for i in range(1, m):
			while j > 0 and pattern[j] != pattern[i]:
				j = pi[j - 1]
			if pattern[j] == pattern[i]:
				j += 1
			pi[i] = j
		j = 0
		indices = []
		for i in range(n):
			while j > 0 and pattern[j] != text[i]:
				j = pi[j - 1]
			if pattern[j] == text[i]:
				j += 1
			if j == m:
				indices.append(i - m + 2)
				j = pi[j - 1]
		if len(indices) == 0:
			indices.append(-1)
		return indices


class Solution:

	def search(self, patt, s):
		m = len(s)
		arr = []
		n = len(patt)
		step = m - n + 1
		for i in range(step):
			if s[i:i + n] == patt:
				arr.append(i + 1)
		if arr != []:
			return arr
		else:
			return [-1]


class Solution:

	def search(self, patt, s):
		d = 256
		q = -2 ** 31 - 1
		window_size = len(patt)
		h = d ** (window_size - 1) % q
		hash_patt = hash_s = 0
		res = []
		for i in range(window_size):
			hash_patt = (hash_patt * d + ord(patt[i])) % q
			hash_s = (hash_s * d + ord(s[i])) % q
		if hash_patt == hash_s:
			res.append(1)
		for i in range(window_size, len(s)):
			old_hash = hash_s - h * ord(s[i - window_size])
			hash_s = (old_hash * d + ord(s[i])) % q
			if hash_patt == hash_s:
				res.append(i - window_size + 1 + 1)
		return res if res else [-1]


class Solution:

	def search(self, patt, s):
		res = []
		haystack = s
		needle = patt
		q = 2 ** 31 - 1
		window_size = len(needle)
		h = 26 ** (window_size - 1) % q
		hash_needle = 0
		for ch in needle:
			hash_needle = (hash_needle * 26 + (ord(ch) - ord('a') + 1)) % q
		hash_hay = 0
		for i in range(window_size):
			hash_hay = (hash_hay * 26 + (ord(haystack[i]) - ord('a') + 1)) % q
		if hash_needle == hash_hay:
			res.append(1)
		for i in range(window_size, len(haystack)):
			old_value = ord(haystack[i - window_size]) - ord('a') + 1
			new_indx = ord(haystack[i]) - ord('a') + 1
			old_hash = hash_hay - h * old_value
			hash_hay = (old_hash * 26 + new_indx) % q
			if hash_needle == hash_hay:
				res.append(i - window_size + 1 + 1)
		return res if res else [-1]


class Solution:

	def search(self, p, s):
		a = []
		i = 0
		n = len(p)
		m = len(s)
		j = m - (n - 1)
		while i <= j:
			if s[i:i + n] == p:
				a.append(i + 1)
			i += 1
		return a if len(a) > 0 else [-1]


class Solution:

	def search(self, patt, s):
		z = []
		if patt not in s:
			return [-1]
		a = s.find(patt)
		z.append(a + 1)
		while a >= 0:
			a = s.find(patt, a + 1)
			if a != -1:
				z.append(a + 1)
		return z


class Solution:

	def search(self, patt, s):
		d = 256
		ans = []

		def search(pat, txt, q):
			M = len(pat)
			N = len(txt)
			i = 0
			j = 0
			p = 0
			t = 0
			h = 1
			for i in range(M - 1):
				h = h * d % q
			for i in range(M):
				p = (d * p + ord(pat[i])) % q
				t = (d * t + ord(txt[i])) % q
			for i in range(N - M + 1):
				if p == t:
					for j in range(M):
						if txt[i + j] != pat[j]:
							break
						else:
							j += 1
					if j == M:
						ans.append(str(i + 1))
				if i < N - M:
					t = (d * (t - ord(txt[i]) * h) + ord(txt[i + M])) % q
					if t < 0:
						t = t + q
		search(patt, s, 101)
		return ans if len(ans) != 0 else [-1]


class Solution:

	def search(self, patt, s):
		ans = []
		(sn, pn) = (len(s), len(patt))
		for i in range(sn - pn + 1):
			if s[i] == patt[0]:
				for j in range(pn):
					if s[i + j] != patt[j]:
						break
				else:
					ans.append(i + 1)
		if not ans:
			return [-1]
		return ans


class Solution:

	def search(self, pat, s):
		n = len(s)
		m = len(pat)
		ans = []
		for i in range(n - m + 1):
			if s[i:i + m] == pat:
				ans.append(i + 1)
		if ans:
			return ans
		return [-1]


class Solution:

	def search(self, b, a):
		n = len(a)
		m = len(b)
		ans = []
		c = 0
		for i in range(n - m + 1):
			t = i
			j = 0
			while j < m and a[t] == b[j]:
				j += 1
				t += 1
			if j == m:
				ans.append(i + 1)
				c = 1
		if c:
			return ans
		return [-1]


class Solution:

	def search(self, pattern, text):
		d = 256
		q = 101
		m = len(pattern)
		n = len(text)
		p_hash = t_hash = 0
		h = 1
		for i in range(m - 1):
			h = h * d % q
		for i in range(m):
			p_hash = (d * p_hash + ord(pattern[i])) % q
			t_hash = (d * t_hash + ord(text[i])) % q
		results = []
		for i in range(n - m + 1):
			if p_hash == t_hash and text[i:i + m] == pattern:
				results.append(i + 1)
			if i < n - m:
				t_hash = (d * (t_hash - ord(text[i]) * h) + ord(text[i + m])) % q
				t_hash = (t_hash + q) % q
		if not results:
			return [-1]
		return results


import re

class Solution:

	def search(self, patt, s):
		res = [i + 1 for i in range(len(s)) if s.startswith(patt, i)]
		if len(res) != 0:
			return res
		else:
			return [-1]


class Solution:

	def search(self, patt, s):
		res = []
		d = 256
		n = len(s)
		m = len(patt)
		h = 1
		p = 0
		t = 0
		q = 101
		for i in range(1, m):
			h = h * d % q
		for i in range(m):
			p = (p * d + ord(patt[i])) % q
			t = (t * d + ord(s[i])) % q
		for i in range(n - m + 1):
			if p == t:
				j = 0
				while j < m:
					if patt[j] != s[i + j]:
						break
					j += 1
				if j == m:
					res.append(i + 1)
			if i < n - m:
				t = (d * (t - ord(s[i]) * h) + ord(s[i + m])) % q
				if t < 0:
					t = t + q
		if len(res) == 0:
			return [-1]
		return res