Given two strings, one is a text string, txt and other is a pattern string, pat. 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:
txt = "batmanandrobinarebat", pat = "bat"
Output: 1 18
Explanation: The string "bat" occurs twice
in txt, one starts are index 1 and the other
at index 18. 
Example 2:
Input: 
txt = "abesdu", pat = "edu"
Output: -1
Explanation: There's not substring "edu"
present in txt.
Your Task:
You don't need to read input or print anything. Your task is to complete the function search() which takes the string txt and the string pat as inputs and returns an array denoting the start indices (1-based) of substring pat in the string txt. 
Note: Return an empty list incase of no occurences of pattern. Driver will print -1 in this case.
Expected Time Complexity: O(|txt|).
Expected Auxiliary Space: O(|txt|).
Constraints:
1 ≤ |txt| ≤ 10^{5}
1 ≤ |pat| < |S|

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def search(self, pat, txt):
        # code here

Solutions:
class Solution:

	def search(self, p, s):
		lp = len(p)
		lps = [0 for i in range(lp)]
		j = 0
		ma = (0, 0)
		for i in range(1, lp):
			if p[i] == p[j]:
				lps[i] = j
				ma = max(ma, (j, i))
				j += 1
			else:
				j = 0
		res = []
		ls = len(s)
		j = i = 0
		while i < ls:
			if s[i] != p[j]:
				if j == 0:
					i += 1
				else:
					j = lps[j]
			else:
				j += 1
				if j == lp:
					res.append(i - lp + 2)
					j = ma[1]
				i += 1
		return res


class Solution:

	def search(self, pat, txt):
		occurences = []
		txt_len = len(txt)
		pat_len = len(pat)
		for i in range(txt_len - pat_len + 1):
			if txt[i:i + pat_len] == pat:
				occurences.append(i + 1)
		return occurences


class Solution:

	def search(self, pat, txt):
		li = []
		for i in range(len(txt) - (len(pat) - 1)):
			if txt[i:i + len(pat)] == pat:
				li.append(i + 1)
		return li


class Solution:

	def search(self, pat, txt):
		LPS = [0] * len(pat)

		def KMP():
			i = 1
			len1 = 0
			while i < len(pat):
				if pat[i] == pat[len1]:
					LPS[i] = len1 + 1
					i += 1
					len1 += 1
				elif len1 != 0:
					len1 = LPS[len1 - 1]
				else:
					LPS[i] = 0
					i += 1

		def search():
			res = []
			i = 0
			j = 0
			while i < len(txt):
				if pat[j] == txt[i]:
					i += 1
					j += 1
				elif j != 0:
					j = LPS[j - 1]
				else:
					i += 1
				if j == len(pat):
					res.append(i - j + 1)
					j = LPS[j - 1]
			return res
		KMP()
		return search()


class Solution:

	def search(self, pat, txt):
		M = len(pat)
		N = len(txt)
		lps = [0] * M
		j = 0
		p = []
		self.computeLPSArray(pat, M, lps)
		i = 0
		while i < N:
			if pat[j] == txt[i]:
				i += 1
				j += 1
			if j == M:
				p.append(i - j + 1)
				j = lps[j - 1]
			elif i < N and pat[j] != txt[i]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
		return p

	def computeLPSArray(self, pat, M, lps):
		len = 0
		lps[0] = 0
		i = 1
		while i < M:
			if pat[i] == pat[len]:
				len += 1
				lps[i] = len
				i += 1
			elif len != 0:
				len = lps[len - 1]
			else:
				lps[i] = 0
				i += 1


class Solution:

	def search(self, pat, txt):
		l = []
		lps = [0 for i in range(len(pat))]

		def computelps(lps, pat, txt):
			M = len(pat)
			i = 1
			lps[0] = 0
			l = 0
			while i < M:
				if pat[i] == pat[l]:
					l += 1
					lps[i] = l
					i += 1
				elif l != 0:
					l = lps[l - 1]
				else:
					lps[i] = 0
					i += 1
		computelps(lps, pat, txt)
		i = 0
		j = 0
		r = []
		while i < len(txt):
			if j < len(pat) and txt[i] == pat[j]:
				i += 1
				j += 1
				r.append(j)
			elif j == len(pat):
				l.append(str(i - (j - 1)))
				j = lps[j - 1]
			elif i < len(txt) and txt[i] != pat[j]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
		if j == len(pat):
			l.append(str(i - (j - 1)))
		return l


class Solution:

	def search(self, pat, txt):
		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 generateLPS(self, pat):
		m = len(pat)
		lps = [0] * m
		j = 1
		length = 0
		while j < m:
			if pat[j] == pat[length]:
				length += 1
				lps[j] = length
				j += 1
			elif length != 0:
				length = lps[length - 1]
			else:
				lps[j] = 0
				j += 1
		return lps

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


class Solution:

	def search(self, pat, txt):
		lps_array = [0] * len(pat)
		(l, i) = (0, 1)
		while i < len(pat):
			if pat[i] == pat[l]:
				l += 1
				lps_array[i] = l
				i += 1
			elif l == 0:
				i += 1
			else:
				l = lps_array[l - 1]
		(i, j) = (0, 0)
		ans = []
		while i < len(txt):
			if txt[i] == pat[j]:
				i += 1
				j += 1
			elif j == 0:
				i += 1
			else:
				j = lps_array[j - 1]
			if j == len(pat):
				ans.append(i - len(pat) + 1)
				j = lps_array[j - 1]
		return ans


def maker(p, np):
	g = [-1]
	i = 0
	j = 1
	while j < np:
		if p[j] == p[i]:
			g.append(i)
			i += 1
			j += 1
		elif i == 0:
			g.append(-1)
			j += 1
		else:
			i = 0
	return g

class Solution:

	def search(self, pat, txt):
		t = txt
		p = pat
		np = len(p)
		nt = len(t)
		guide = maker(p, np)
		i = 0
		j = -1
		store = []
		while i < nt:
			if t[i] == p[j + 1]:
				if j + 2 == np:
					store.append(i - np + 2)
					i += 1
					j = guide[j + 1]
				else:
					i += 1
					j += 1
			elif j == -1:
				i += 1
			else:
				j = guide[j]
		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, pat, txt):
		(PN, TN) = (len(pat), len(txt))
		lps = [0] * PN
		ans = []
		for i in range(1, PN):
			ix = lps[i - 1]
			while ix > 0 and pat[i] != pat[ix]:
				ix = lps[ix - 1]
			lps[i] = lps[ix] + (1 if pat[i] == pat[ix] else 0)
		k = 0
		for i in range(TN):
			while k > 0 and txt[i] != pat[k]:
				k = lps[k - 1]
			k += 1 if txt[i] == pat[k] else 0
			if k == PN:
				ans.append(i - PN + 2)
				k = lps[k - 1]
		return ans


class Solution:

	def getlps(self, s, n):
		i = 1
		l = 0
		lps = [0] * n
		while i < n:
			if s[i] == s[l]:
				l += 1
				lps[i] = l
				i += 1
			else:
				if l == 0:
					lps[i] = 0
					i += 1
				l = lps[l - 1]
		return lps

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


class Solution:

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


class Solution:

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


class Solution:

	def search(self, pat, txt):

		def z_alg(s: str) -> list:

			def compare(s, a, b):
				while a < len(s) and s[a] == s[a - b]:
					a += 1
				return a
			n = len(s)
			(z_arr, l, r) = ([None] * n, 0, 0)
			for k in range(1, n):
				if k > r:
					(l, r) = (k, k)
					r = compare(s, r, l)
					z_arr[k] = r - l
					r -= 1
				elif z_arr[k - l] < r - k + 1:
					z_arr[k] = z_arr[k - l]
				else:
					l = k
					r = compare(s, r, l)
					z_arr[k] = r - l
					r -= 1
			return z_arr

		def find_bad_char(pat: str, txt: str) -> list:
			bad_char = dict()
			for char in set(txt):
				bad_char[char] = 0
			for i in range(len(pat)):
				bad_char[pat[i]] = i + 1
			return bad_char

		def find_good_suffix(pat: str) -> list:
			m = len(pat)
			z_suffix = z_alg(pat[::-1])[::-1]
			good_suffix = [0 for _ in range(m + 1)]
			for p in range(1, m - 1):
				good_suffix[m - z_suffix[p]] = p + 1
			return good_suffix

		def find_matched_prefix(pat: str) -> list:
			m = len(pat)
			z = z_alg(pat)
			z[0] = m
			z.append(0)
			for i in range(m - 1, -1, -1):
				z[i] = max(z[i], z[i + 1])
			return z

		def boyer_moore(pat, txt):
			(m, n) = (len(pat), len(txt))
			res = []
			if m > n:
				return res
			bad_char = find_bad_char(pat, txt)
			good_suffix = find_good_suffix(pat)
			matched_prefix = find_matched_prefix(pat)
			shift = 0
			while shift <= n - m:
				k = m - 1
				while k >= 0 and pat[k] == txt[shift + k]:
					k -= 1
				if k < 0:
					res.append(shift + 1)
					shift += max(1, m - matched_prefix[1])
				else:
					bad_char_shift = k - bad_char[txt[shift + k]]
					gs = good_suffix[k + 1]
					if k < m and gs > 0:
						good_suffix_shift = m - gs - 1
					else:
						good_suffix_shift = m - matched_prefix[k + 1] - 1
					shift += max(1, bad_char_shift, good_suffix_shift)
			return res
		return boyer_moore(pat, txt)


class Solution:

	def search(self, target, s):
		if target == s:
			return 0
		n = len(target)
		res = [0 for i in range(n)]
		i = 0
		j = 1
		while j < n:
			if target[j] == target[i]:
				res[j] = i + 1
				i += 1
				j += 1
			elif i == 0:
				res[j] = 0
				j += 1
			else:
				i = res[i - 1]
		ans = []
		i = j = 0
		n = len(s)
		while j < n:
			if i == len(target):
				i = 0
				ans.append(j - len(target) + 1)
				j = j - len(target) + 1
			if s[j] == target[i]:
				i += 1
				j += 1
			elif i == 0:
				j += 1
			else:
				i = res[i - 1]
		if i == len(target):
			i = 0
			ans.append(j - len(target) + 1)
		return ans


class Solution:

	def search(self, s, txt):
		if s == txt:
			return 0
		res = [0] * len(s)
		i = 0
		j = i + 1
		while j < len(s):
			if s[i] == s[j]:
				res[j] = i + 1
				i += 1
				j += 1
			elif i == 0:
				res[j] = 0
				j += 1
			else:
				i = res[i - 1]
		i = 0
		j = 0
		ans = []
		while j < len(txt):
			if i == len(s):
				i = 0
				ans.append(j - len(s) + 1)
				j = j - len(s) + 1
			if s[i] == txt[j]:
				i += 1
				j += 1
			elif i == 0:
				j += 1
			else:
				i = res[i - 1]
		else:
			if i == len(s):
				i = 0
				ans.append(j - len(s) + 1)
		return ans


class Solution:

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


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
		for i in ind:
			l.append(i + 1)
		return l


class Solution:

	def lpss(pat, txt):
		lps = [0] * len(pat)
		i = 1
		prev = 0
		while i < len(pat):
			if pat[i] == pat[prev]:
				prev += 1
				lps[i] = prev
				i += 1
			elif prev == 0:
				lps[i] = 0
				i += 1
			else:
				prev = lps[prev - 1]
		return lps

	def search(self, pat, txt):
		lps = Solution.lpss(pat, txt)
		res = []
		i = 0
		j = 0
		N = len(txt)
		M = len(pat)
		while N - i >= M - j:
			if txt[i] == pat[j]:
				i += 1
				j += 1
			if j == M:
				res.append(i - j + 1)
				j = lps[j - 1]
			elif i < N and pat[j] != txt[i]:
				if j == 0:
					i += 1
				else:
					j = lps[j - 1]
		return res


class Solution:

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


class Solution:

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


class Solution:

	def search(self, k, ip):
		i = 0
		ls = []
		ipn = len(ip)
		kn = len(k)
		while i <= ipn - kn:
			j = 0
			while j < kn:
				if k[j] != ip[i + j]:
					break
				j += 1
			if j == kn:
				ls.append(i + 1)
			i += 1
		return ls


class Solution:

	def search(self, pat, txt):
		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, pat, txt):
		haystack = txt
		needle = pat
		m = len(haystack)
		n = len(needle)
		lps = [0] * n
		cur = 1
		prev = 0
		while cur < n:
			if needle[cur] == needle[prev]:
				prev += 1
				lps[cur] = prev
				cur += 1
			elif prev == 0:
				lps[cur] = 0
				cur += 1
			else:
				prev = lps[prev - 1]
		ans = []
		hay = 0
		nee = 0
		while hay < m:
			if haystack[hay] == needle[nee]:
				hay += 1
				nee += 1
			elif nee == 0:
				hay += 1
			else:
				nee = lps[nee - 1]
			if nee == n:
				ans.append(hay - nee + 1)
				nee = lps[nee - 1]
		return ans


class Solution:

	def search(self, pat, txt):
		(N, M) = (len(txt), len(pat))
		pref = [0] * M
		(i, j) = (1, 0)
		while i < len(pat):
			if pat[i] == pat[j]:
				j += 1
				pref[i] = j
				i += 1
			elif j != 0:
				j = pref[j - 1]
			else:
				pref[i] = 0
				i += 1
		(i, j) = (0, 0)
		ans = []
		i = 0
		while N - i >= M - j:
			if i >= N or j >= M:
				break
			if pat[j] == txt[i]:
				i += 1
				j += 1
			if j == M:
				ans.append(i - j + 1)
				j = pref[j - 1]
			elif i < N and pat[j] != txt[i]:
				if j != 0:
					j = pref[j - 1]
				else:
					i += 1
		if len(ans) > 0:
			return ans
		else:
			return [-1]


def lps(pat, Lps, m):
	Lps[0] = 0
	l = 0
	i = 1
	while i < m:
		if pat[l] == pat[i]:
			l += 1
			Lps[i] = l
			i += 1
		elif l != 0:
			l = Lps[l - 1]
		else:
			Lps[i] = 0
			i += 1

class Solution:

	def search(self, pat, txt):
		n = len(txt)
		m = len(pat)
		i = 0
		j = 0
		res = []
		Lps = [0] * m
		lps(pat, Lps, m)
		while i < n:
			if txt[i] == pat[j]:
				j += 1
				i += 1
			if j == m:
				res.append(i - j + 1)
				j = Lps[j - 1]
			elif i < n and txt[i] != pat[j]:
				if j != 0:
					j = Lps[j - 1]
				else:
					i += 1
		if len(res) == 0:
			return [-1]
		return res


class Solution:

	def search(self, pat, txt):
		n = len(txt)
		k = len(pat)
		occur = []
		if pat == '':
			return occur
		lps = [0] * k
		(prevLPS, i) = (0, 1)
		while i < k:
			if pat[i] == pat[prevLPS]:
				lps[i] = prevLPS + 1
				prevLPS += 1
				i += 1
			elif prevLPS == 0:
				lps[i] = 0
				i += 1
			else:
				prevLPS = lps[prevLPS - 1]
		(i, j) = (0, 0)
		while i < n:
			if txt[i] == pat[j]:
				i += 1
				j += 1
			elif j == 0:
				i += 1
			else:
				j = lps[j - 1]
			if j == k:
				occur.append(i - k + 1)
				j = lps[j - 1]
		return occur


class Solution:

	def search(self, pat, txt):
		n = len(txt)
		k = len(pat)
		occur = []
		for window in range(n - k + 1):
			for i in range(k):
				if pat[i] != txt[window + i]:
					break
				if i == k - 1:
					occur.append(window + 1)
		return occur


class Solution:

	def search(self, pat, txt):
		res = []
		Lmp = [0] * len(pat)
		self.constructLmp(pat, Lmp)
		n = len(pat)
		m = len(txt)
		i = 0
		j = 0
		while m - j >= n - i:
			if pat[i] == txt[j]:
				i += 1
				j += 1
			if i == n:
				res.append(j + 1 - i)
				i = Lmp[i - 1]
			elif j < m and pat[i] != txt[j]:
				if i != 0:
					i = Lmp[i - 1]
				else:
					j += 1
		return res

	def constructLmp(self, pat, Lmp):
		Lmp[0] = 0
		i = 0
		j = 1
		while j < len(pat):
			if pat[i] == pat[j]:
				i += 1
				Lmp[j] = i
				j += 1
			elif i != 0:
				i = Lmp[i - 1]
			else:
				j += 1


def buildkmp(arr):
	kmp = [0] * len(arr)
	kmp[0] = 0
	for i in range(1, len(arr)):
		cur = kmp[i - 1]
		while cur >= 0:
			if arr[i] == arr[cur]:
				kmp[i] = cur + 1
				break
			elif cur > 1:
				cur = kmp[cur - 1]
			else:
				break
	return kmp

class Solution:

	def search(self, pat, txt):
		kmp = buildkmp(pat)
		out = []
		i = j = 0
		while j <= len(txt):
			if i >= len(pat):
				out.append(j - len(pat) + 1)
				i = kmp[i - 1]
			elif j >= len(txt):
				break
			elif pat[i] == txt[j]:
				i += 1
				j += 1
			elif i > 1:
				i = kmp[i - 1]
			elif i == 0:
				j += 1
			elif i == 1:
				i = 0
			else:
				raise ValueError('khutish')
		return out


def lpwias(s):
	lps = [0 for k in range(len(s))]
	i = 1
	j = 0
	while i < len(s):
		if s[i] == s[j]:
			lps[i] = j + 1
			i += 1
			j += 1
		else:
			if j == 0:
				lps[i] = 0
				i += 1
				continue
			j = lps[j - 1]
	return lps

def kmp(pat, s):
	lps = lpwias(pat)
	i = 0
	j = 0
	res = []
	while i < len(s):
		if s[i] == pat[j]:
			i += 1
			j += 1
			if j == len(pat):
				res.append(i - len(pat) + 1)
				j = lps[j - 1]
		else:
			if j == 0:
				i += 1
				continue
			j = lps[j - 1]
	return res

class Solution:

	def search(self, pat, txt):
		return kmp(pat, s)


class Solution:

	def search(self, pat, txt):
		a = 0
		b = len(patt)
		arr = []
		while b <= len(s):
			if s[a:b] == patt:
				arr.append(a + 1)
			a += 1
			b += 1
		if len(arr) == 0:
			arr.append(-1)
		return arr


def LPS(s, lps):
	n = len(s)
	lps[0] = 0
	(i, l) = (1, 0)
	while i < n:
		if s[i] == s[l]:
			l += 1
			lps[i] = l
			i += 1
		elif l == 0:
			lps[i] = l
			i += 1
		else:
			l = lps[l - 1]

class Solution:

	def search(self, pat, txt):
		(n, m) = (len(txt), len(pat))
		(a, b) = (txt, pat)
		(lps, index) = ([0] * m, [])
		LPS(b, lps)
		i = j = 0
		while i < n:
			if a[i] == b[j]:
				i += 1
				j += 1
			if j == m:
				index.append(i - j + 1)
				j = lps[j - 1]
			elif i < n and a[i] != b[j]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
		return index


class Solution:

	def search(self, pat, txt):

		def computelps(pat, M):
			le = 0
			i = 1
			lps[0] = 0
			while i < M:
				if pat[i] == pat[le]:
					lps[i] = le + 1
					le += 1
					i += 1
				elif le != 0:
					le = lps[le - 1]
				else:
					lps[i] = 0
					i += 1
		n = len(txt)
		M = len(pat)
		lps = [0] * M
		computelps(pat, M)
		ans = []
		i = 0
		j = 0
		while n - i >= M - j:
			if txt[i] == pat[j]:
				i += 1
				j += 1
			elif i < n and txt[i] != pat[j]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
			if j == M:
				ans.append(i - j + 1)
				j = lps[j - 1]
		return ans if len(ans) > 0 else [-1]


class Solution:

	def search(self, pat, txt):
		self.text = '$' + txt
		self.patron = '$' + pat
		self.pi = [0 for _ in range(len(self.patron) + 3)]
		self.__prefix_function()
		ocu = self.kmp()
		return ocu

	def __prefix_function(self) -> None:
		k = 0
		for i in range(2, len(self.patron)):
			while k > 0 and self.patron[k + 1] != self.patron[i]:
				k = self.pi[k]
			if self.patron[k + 1] == self.patron[i]:
				k += 1
			self.pi[i] = k

	def kmp(self) -> list:
		(occurrences, k) = ([], 0)
		for i in range(1, len(self.text)):
			while k > 0 and self.text[i] != self.patron[k + 1]:
				k = self.pi[k]
			if self.text[i] == self.patron[k + 1]:
				k += 1
			if k == len(self.patron) - 1:
				occurrences.append(i - len(self.patron) + 2)
				k = self.pi[k]
		return occurrences


class Solution:

	def search(self, pat, txt):
		l = []
		end = 0
		n = len(txt)
		tmp = ''
		p = len(pat)
		st = 0
		while end <= n - 1:
			while len(tmp) != p:
				tmp += s[end]
				end += 1
			if tmp == pat:
				l.append(end - (len(tmp) - 1))
				tmp = tmp.replace(s[st], '', 1)
				st += 1
			else:
				tmp = tmp.replace(s[st], '', 1)
				st += 1
		if len(l) == 0:
			return [-1]
		else:
			return l


class Solution:

	def search(self, pat, txt):
		n = len(txt)
		m = len(pat)
		pi = [0] * m
		(i, j) = (0, 1)
		while i < m and j < m:
			if pat[i] == pat[j]:
				pi[j] = i + 1
				i += 1
			else:
				i = 0
			j += 1
		i = j = 0
		ret = []
		while n - i >= m - j:
			if txt[i] == pat[j]:
				i += 1
				j += 1
			if j == m:
				ret.append(i - j + 1)
				j = pi[j - 1]
			elif i < n and pat[j] != txt[i]:
				if j != 0:
					j = pi[j - 1]
				else:
					i += 1
		return ret


class Solution:

	def search(self, pat, txt):
		d = dict()
		a = [-1] * len(pat)
		k = len(pat)
		for i in range(len(pat)):
			if pat[i] in d:
				if i - 1 >= 0 and a[i - 1] + 1 == d[pat[i]]:
					a[i] = d[pat[i]]
				elif d[pat[i]] == 0:
					a[i] = 0
			else:
				d[pat[i]] = i
		del d
		i = 0
		j = 0
		ans = []
		m = 0
		while i < len(txt):
			x = i - m
			ins = False
			while i < len(txt) and j < k and (pat[j] == txt[i]):
				ins = True
				j += 1
				i += 1
				m += 1
			if ins:
				if m == k:
					ans.append(x + 1)
					j = a[j - 1] + 1
					m = j
				elif a[j - 1] != -1:
					j = a[j - 1] + 1
					m = j
				else:
					j = 0
					m = 0
			if not ins:
				j = 0
				m = 0
				i += 1
		return ans


class Solution:

	def search(self, pat, txt):
		indexes = []
		for (i, c) in enumerate(s):
			if c == patt[0] and s[i:i + len(patt)] == patt:
				indexes.append(i + 1)
		return indexes if indexes else [-1]


class Solution:

	def search(self, pat, txt):
		l = 0
		r = 0
		res = []
		while r < len(txt):
			if r + 1 < len(pat):
				r += 1
			elif r + 1 >= len(pat):
				if txt[l:r + 1] == pat:
					res.append(l + 1)
				l += 1
				r += 1
		return res if len(res) != 0 else [-1]


class Solution:

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


def lps(s):
	n = len(s)
	LPS = [0] * n
	start = 0
	i = 1
	while i < n:
		if s[i] == s[start]:
			start += 1
			LPS[i] = start
			i += 1
		elif start != 0:
			start = LPS[start - 1]
		else:
			LPS[i] = 0
			i += 1
	return LPS

class Solution:

	def search(self, pat, txt):
		new = pat + '@' + txt
		LPS = lps(new)
		n = len(pat)
		LPS = LPS[n:]
		ans = []
		for i in range(0, len(LPS)):
			if LPS[i] == n:
				ans.append(i - n + 1)
		return ans


class Solution:

	def search(self, pat, txt):

		def prefixF(p):
			n = len(p)
			pi = [0 for i in range(n)]
			c = 0
			for i in range(1, n):
				while p[i] != p[c] and c > 0:
					c = pi[c - 1]
				if p[c] == p[i]:
					c += 1
				pi[i] = c
			return pi

		def kmp(p, t):
			(n, m) = (len(p), len(t))
			pi = prefixF(p)
			q = 0
			s = []
			for i in range(m):
				while p[q] != t[i] and q > 0:
					q = pi[q - 1]
				if p[q] == t[i]:
					q += 1
				if q == n:
					s.append(i - n + 1)
					q = pi[q - 1]
			return s
		return list(map(lambda x: x + 1, kmp(pat, txt)))


class Solution:

	def search(self, patt, s):
		lps = getLPS(patt)
		(mainI, pattI) = (0, 0)
		ansArr = []
		while mainI < len(s):
			if s[mainI] == patt[pattI]:
				mainI += 1
				pattI += 1
			elif pattI == 0:
				mainI += 1
			else:
				pattI = lps[pattI - 1]
			if pattI == len(patt):
				ansArr.append(mainI - len(patt) + 1)
				pattI = lps[pattI - 1]
		return ansArr

def getLPS(patt):
	lps = [0] * len(patt)
	i = 1
	lenSoFar = 0
	while i < len(patt):
		if patt[i] == patt[lenSoFar]:
			lps[i] = lenSoFar + 1
			i += 1
			lenSoFar += 1
		elif lenSoFar == 0:
			i += 1
		else:
			lenSoFar = lps[lenSoFar - 1]
	return lps


class Solution:

	def lps(self, s):
		arr = []
		leng = 0
		arr.append(leng)
		j = 1
		while j < len(s):
			if s[j] == s[leng]:
				leng += 1
				arr.append(leng)
				j += 1
			elif leng == 0:
				arr.append(0)
				j += 1
			else:
				leng = arr[leng - 1]
		return arr

	def search(self, pat, txt):
		arr = self.lps(pat)
		res = []
		i = 0
		j = 0
		while i < len(txt):
			if txt[i] == pat[j]:
				i += 1
				j += 1
				if j == len(pat):
					res.append(i - j + 1)
					j = arr[j - 1]
			elif j == 0:
				i += 1
			else:
				j = arr[j - 1]
		if len(res) > 0:
			return res
		else:
			return [-1]


class Solution:

	def search(self, pat, txt):
		i = 0
		res = []
		while i <= len(txt) - len(patt):
			if txt[i] == patt[0] and txt[i + len(patt) - 1] == patt[len(patt) - 1]:
				if txt[i:i + len(patt)] == patt:
					res.append(i + 1)
			i += 1
		if len(res) > 0:
			return res
		else:
			return [-1]


class Solution:

	def search(self, pat, txt):
		ans = []

		def get_lps(s, size):
			lps = [0 for _ in range(size)]
			prev = 0
			i = 1
			while i < size:
				if s[i] == s[prev]:
					prev += 1
					lps[i] = prev
					i += 1
				elif prev == 0:
					lps[i] = 0
					i += 1
				else:
					prev = lps[prev - 1]
			return lps
		lps = get_lps(pat, len(pat))
		i = j = 0
		while i < len(txt):
			if txt[i] == pat[j]:
				i += 1
				j += 1
			if j >= len(pat):
				ans.append(i - len(pat) + 1)
				j = lps[j - 1]
			elif i < len(txt) and txt[i] != pat[j]:
				if j == 0:
					i += 1
				else:
					j = lps[j - 1]
		return ans


class Solution:

	def search(self, p, s):

		def computeLPS(p, n, lps):
			i = 1
			j = 0
			while i < n and j < n:
				if p[i] == p[j]:
					lps[i] = j + 1
					i += 1
					j += 1
				else:
					j = lps[j - 1]
					if j == 0:
						lps[i] = 0
						i += 1
			return lps
		m = len(s)
		n = len(p)
		lps = [0] * n
		computeLPS(p, n, lps)
		i = 0
		j = 0
		ans = []
		while i < m and j < n:
			if s[i] == p[j]:
				i += 1
				j += 1
			if j == n:
				ans.append(i - j + 1)
				j = lps[j - 1]
			elif i < m and s[i] != p[j]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
		return ans


class Solution:

	def search(self, pat, txt):
		l = []
		(n, m) = (len(txt), len(pat))
		if pat not in txt:
			return l
		else:
			for i in range(n - m + 1):
				if pat == txt[i:i + m]:
					l.append(i + 1)
		return l
		n = len(txt)
		m = len(pat)
		lps = [0] * m
		j = 0
		ma = (0, 0)
		for i in range(1, m):
			if pat[i] == pat[j]:
				lps[i] = j
				ma = max(ma, (j, i))
				j += 1
			else:
				j = 0
		res = []
		j = i = 0
		while i < n:
			if txt[i] != pat[j]:
				if j == 0:
					i += 1
				else:
					j = lps[j]
			else:
				j += 1
				if j == m:
					res.append(i - m + 2)
					j = ma[1]
				i += 1
		return res


class Solution:

	def search(self, pat, txt):
		lis = []
		pos = txt.find(pat)
		while pos >= 0:
			lis.append(pos + 1)
			pos = txt.find(pat, pos + 1)
		return lis


class Solution:

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


class Solution:

	def search(self, pat, txt):
		a = 0
		l = []
		while a != -1:
			a = txt.find(pat, a)
			if a != -1:
				l.append(a + 1)
				a += 1
			else:
				break
		return l


class Solution:

	def search(self, pat, txt):
		separator = '#'
		string = pat + separator + txt

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


class Solution:

	def search(self, pattern, txt):
		ret = [0]
		for i in range(1, len(pattern)):
			j = ret[i - 1]
			while j > 0 and pattern[j] != pattern[i]:
				j = ret[j - 1]
			ret.append(j + 1 if pattern[j] == pattern[i] else j)
		partial = ret
		(ret, j) = ([], 0)
		for i in range(len(txt)):
			while j > 0 and txt[i] != pattern[j]:
				j = partial[j - 1]
			if txt[i] == pattern[j]:
				j += 1
			if j == len(pattern):
				ret.append(i - (j - 1))
				j = partial[j - 1]
		a = []
		for i in ret:
			a.append(i + 1)
		return a


class Solution:

	def lps(self, pat, n, lps):
		len = 0
		j = 1
		while j < n:
			if pat[len] == pat[j]:
				lps[j] = len + 1
				j += 1
				len += 1
			elif len != 0:
				len = lps[len - 1]
			else:
				j += 1

	def search(self, pat, txt):
		N = len(txt)
		M = len(pat)
		res = []
		lps = [0] * M
		self.lps(pat, M, lps)
		i = 0
		j = 0
		while i < N:
			if txt[i] == pat[j]:
				i += 1
				j += 1
			elif j != 0:
				j = lps[j - 1]
			else:
				i += 1
			if j == M:
				res.append(i - j + 1)
				j = lps[j - 1]
		return res


class Solution:

	def search(self, pat, txt):
		M = len(pat)
		N = len(txt)
		pi = [0 for i in range(len(pat))]
		d = {}
		for i in range(len(pat)):
			if pat[i] in pat[:i]:
				pi[i] = d[pat[i]]
			d[pat[i]] = d.get(pat[i], 0) + 1
		ans = []
		j = 0
		i = 0
		while N - i >= M - j:
			if pat[j] == txt[i]:
				i += 1
				j += 1
			if j == M:
				ans.append(i - j + 1)
				j = pi[j - 1]
			elif i < N and pat[j] != txt[i]:
				if j != 0:
					j = pi[j - 1]
				else:
					i += 1
		return ans


class Solution:

	def search(self, pat, txt):
		return solve(pat, txt)

def computeLPSArray(pattern):
	(l, i) = (0, 1)
	N = len(pattern)
	lps = [0] * N
	while i < N:
		if pattern[i] == pattern[l]:
			lps[i] = l + 1
			i += 1
			l += 1
		elif l != 0:
			l = lps[l - 1]
		else:
			lps[i] = 0
			i += 1
	return lps

def solve(pattern, s):
	lps = computeLPSArray(pattern)
	(M, N) = (len(pattern), len(s))
	(i, j) = (0, 0)
	ans = []
	while i < N:
		if s[i] == pattern[j]:
			i += 1
			j += 1
		elif j != 0:
			j = lps[j - 1]
		else:
			i += 1
		if j == M:
			ans.append(i - M + 1)
			j = lps[j - 1]
	return ans


class Solution:

	def failure_function(self, pattern):
		n = len(pattern)
		h = [0] * n
		(j, i) = (0, 1)
		h[0] = 0
		while i < n:
			if pattern[i] == pattern[j]:
				h[i] = j + 1
				i += 1
				j += 1
				continue
			else:
				while pattern[i] != pattern[j]:
					if j > 0:
						j = h[j - 1]
					else:
						j = -1
						break
				h[i] = j + 1
				i += 1
				j += 1
		return h

	def search(self, pattern, text):
		h = self.failure_function(pattern)
		(i, j) = (0, 0)
		answers = []
		(m, n) = (len(pattern), len(text))
		while i < len(text):
			while text[i] == pattern[j]:
				if j == m - 1:
					answers.append(i - m + 2)
					j = h[j] - 1
				(i, j) = (i + 1, j + 1)
				if i == n:
					return answers
			while text[i] != pattern[j]:
				if j > 0:
					j = h[j - 1]
				else:
					j -= 1
					break
			(i, j) = (i + 1, j + 1)
		return answers


class Solution:

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


class Solution:

	def LPSTable(self, pat):
		n = len(pat)
		lps = [0] * len(pat)
		j = 0
		i = 1
		while i < n:
			if pat[i] == pat[j]:
				j += 1
				lps[i] = j
				i += 1
			elif j == 0:
				lps[i] = 0
				i += 1
			else:
				j = lps[j - 1]
		return lps

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


class Solution:

	def search(self, pat, txt):
		k = []
		if len(pat) > len(txt):
			return k
		for i in range(len(txt) - len(pat) + 1):
			kp = txt[i:i + len(pat)]
			j = 0
			while j < len(pat):
				if kp[j] == pat[j]:
					j += 1
				else:
					break
			if j == len(pat):
				k.append(i + 1)
		return k


class Solution:

	def computeLPSArray(self, pat, M, lps):
		length = 0
		lps[0] = 0
		i = 1
		while i < M:
			if pat[i] == pat[length]:
				length += 1
				lps[i] = length
				i += 1
			elif length != 0:
				length = lps[length - 1]
			else:
				lps[i] = 0
				i += 1

	def search(self, pat, txt):
		res = []
		M = len(pat)
		N = len(txt)
		lps = [0 for i in range(M + 1)]
		j = 0
		self.computeLPSArray(pat, M, lps)
		f = 0
		i = 0
		while i < N:
			if pat[j] == txt[i]:
				j += 1
				i += 1
			if j == M:
				f += 1
				res.append(i - j + 1)
				j = lps[j - 1]
			elif i < N and pat[j] != txt[i]:
				if j != 0:
					j = lps[j - 1]
				else:
					i = i + 1
		if f == 0:
			res.append(-1)
		return res


class Solution:

	def search(self, pat, txt):
		ans = []
		lps = [0] * len(pat)
		i = 1
		j = 0
		while i < len(pat):
			if pat[i] == pat[j]:
				lps[i] = j + 1
				i += 1
				j += 1
			elif j == 0:
				lps[i] = 0
				i += 1
			else:
				j = lps[j - 1]
		i = 0
		j = 0
		while i < len(txt):
			if i < len(txt) and j < len(pat) and (txt[i] == pat[j]):
				i += 1
				j += 1
			elif j == 0:
				i += 1
			else:
				j = lps[j - 1]
			if j == len(pat):
				ans.append(i - len(pat) + 1)
		return ans


class Solution:

	def search(self, pat, txt):
		M = len(pat)
		lps = [0] * M
		j = 0
		for i in range(1, M):
			while True:
				if pat[i] == pat[j]:
					j += 1
					lps[i] = j
					break
				else:
					if j == 0:
						break
					j = lps[j - 1]
		ans = []
		N = len(txt)
		i = j = 0
		while i < N:
			if txt[i] == pat[j]:
				j += 1
				i += 1
				if j == M:
					ans.append(i - M + 1)
					j = lps[j - 1]
			elif j == 0:
				i += 1
			else:
				j = lps[j - 1]
		return ans