Given two strings, one is a text string and the other is a pattern string. The task is to print the indexes of all the occurrences of the 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. 
Note: You don't need to return -1 yourself when there are no possible answers, just return an empty list.
Expected Time Complexity: O(|S|).
Expected Auxiliary Space: O(|S|).
Constraints:
1 ≤ |S| ≤ 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, patt, s):

        # code here

Solutions:
class Solution:

	def z_function(self, s):
		n = len(s)
		z = [0] * n
		(l, r) = (0, 0)
		for i in range(1, n):
			if i < r:
				z[i] = min(z[i - l], r - i)
			while z[i] + i < n and s[z[i]] == s[i + z[i]]:
				z[i] += 1
			if i + z[i] > r:
				r = i + z[i]
				l = i
		return z

	def search(self, patt, s):
		z = self.z_function(patt + '$' + s)
		n = len(patt)
		ans = []
		for i in range(n + 1, len(z)):
			if z[i] == n:
				ans.append(i - n)
		return ans


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def zfunc(self, string):
		n = len(string)
		res = [0] * n
		left = 0
		right = 0
		for i in range(1, n):
			if i > right:
				right = i
				left = i
				while right < n and string[right] == string[right - left]:
					right += 1
				res[i] = right - left
				right -= 1
			else:
				il = i - left
				if res[il] < right - i + 1:
					res[i] = res[il]
				else:
					left = i
					while right < n and string[right] == string[right - left]:
						right += 1
					res[i] = right - left
					right -= 1
		return res

	def search(self, patt, s):
		string = patt + '#' + s
		z = self.zfunc(string)
		ans = []
		for i in range(len(z)):
			if z[i] == len(patt):
				ans.append(i - len(patt))
		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, 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 getZarr(self, string, z):
		n = len(string)
		(l, r, k) = (0, 0, 0)
		for i in range(1, n):
			if i > r:
				(l, r) = (i, i)
				while r < n and string[r - l] == string[r]:
					r += 1
				z[i] = r - l
				r -= 1
			else:
				k = i - l
				if z[k] < r - i + 1:
					z[i] = z[k]
				else:
					l = i
					while r < n and string[r - l] == string[r]:
						r += 1
					z[i] = r - l
					r -= 1

	def search(self, pattern, text):
		ans = []
		concat = pattern + '$' + text
		l = len(concat)
		z = [0] * l
		self.getZarr(concat, z)
		for i in range(l):
			if z[i] == len(pattern):
				ans.append(i - len(pattern))
		return ans


def z_alg(str):
	n = len(str)
	z = [None] * n
	r = 0
	l = 0
	q = 0
	for k in range(1, n):
		if k > r:
			q = k
			while q < n and str[q] == str[q - k]:
				q += 1
			z[k] = q - k
			if q != k:
				r = q - 1
				l = k
		else:
			transposed_z = z[k - l]
			transposed_r = r - k + 1
			if transposed_z < transposed_r:
				z[k] = transposed_z
			elif transposed_z > transposed_r:
				z[k] = transposed_r
			else:
				for q in range(r + 1, n + 1):
					if q == n or str[q] != str[q - k]:
						z[k] = q - k
						r = q - 1
						l = k
						break
	return z

def z_alg_search(pat, txt):
	z_arr = z_alg(pat + '$' + txt)
	m = len(pat)
	txt_start = m + 1
	o = []
	for i in range(txt_start, len(z_arr)):
		if z_arr[i] >= m:
			o.append(i - txt_start + 1)
	return o

class Solution:

	def search(self, patt, s):
		return z_alg_search(patt, s)


class Solution:

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


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 search(self, patt, s):

		def compare(s, a, b):
			while a < len(s) and s[a] == s[a - b]:
				a += 1
			return a

		def z_alg(s):
			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 pat_match(pat: str, txt: str) -> int:
			res = []
			s = pat + '$' + txt
			m = len(pat)
			z_arr = z_alg(s)
			for i in range(len(z_arr)):
				if i >= m + 1 and z_arr[i] == m:
					res.append(i - (m + 1) + 1)
			return res
		return pat_match(patt, s)


def bad_char_preprocess(pat):
	if len(pat) < 2:
		return {}
	res = {}
	check = {}
	for i in range(len(pat) - 1):
		check[pat[i]] = i + 1
		res[i + 1] = check.copy()
	return res

def z_box(txt):
	box = [0]
	(n, l, r, k) = (len(txt), 0, 0, 0)

	def magic(l, r, box, i):
		(l, r) = (i, i)
		for j in range(n):
			if i + j >= len(txt) or txt[j] != txt[i + j]:
				break
			else:
				r += 1
		box[i] = r - l
		return (l, r - 1)
	for i in range(1, n):
		box.append(0)
		if i > r:
			(l, r) = magic(l, r, box, i)
		else:
			k = i - l
			if box[k] < r - i + 1:
				box[i] = box[k]
			elif box[k] == r - i + 1:
				(l, r) = magic(l, r, box, i)
			else:
				box[i] = r - i + 1
	return box[1:]

def good_suffix(pat):
	zsuf = z_box(pat[::-1] + '$' + pat[::-1])[len(pat) + 1:][::-1]
	gs = [0 for _ in range(len(pat) + 1)]
	for z in range(len(zsuf)):
		j = len(pat) - zsuf[z]
		gs[j] = z + 1
	return gs

def matched_prefix(pat):
	zsuf = z_box(pat + '$' + pat)[len(pat):]
	mp = [0 for _ in range(len(pat) + 1)]
	for i in range(len(zsuf) - 1, -1, -1):
		mp[i] = max(zsuf[i], mp[i + 1])
	return mp

def get_last(preBad, pos, c):
	if preBad.get(pos) and preBad[pos].get(c):
		return preBad[pos][c]
	else:
		return 0

def boyer_moore(pat, txt):
	preBad = bad_char_preprocess(pat)
	m = len(pat) - 1
	(i, j) = (m, m)
	cur = m
	(start, stop) = (0, 0)
	res = []
	while i < len(txt):
		if pat[j] == txt[i]:
			if j == 0:
				res.append(i + 1)
				i = cur + 1
				j = m
				cur = i
			else:
				j -= 1
				i -= 1
		else:
			i += m - get_last(preBad, j, txt[i]) + 1
			j = m
			cur = i
	return res

class Solution:

	def search(self, patt, s):
		return boyer_moore(patt, s)


class Solution:

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


class Solution:

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


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):
		res = []
		for i in range(len(s) - len(patt) + 1):
			if s[i:i + len(patt)] == patt:
				res.append(i + 1)
		if res:
			return res
		return [-1]


class Solution:

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


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, pattern, text):
		concat = pattern + '$' + text
		left = len(concat)
		z = [0] * left
		self.create_Zarr(concat, z)
		indices = []
		for i in range(left):
			if z[i] == len(pattern):
				indices.append(i - len(pattern))
		return indices

	def create_Zarr(self, string, z):
		n = len(string)
		(left, right, k) = (0, 0, 0)
		for i in range(1, n):
			if i > right:
				(left, right) = (i, i)
				while right < n and string[right - left] == string[right]:
					right += 1
				z[i] = right - left
				right -= 1
			else:
				k = i - left
				if z[k] < right - i + 1:
					z[i] = z[k]
				else:
					left = i
					while right < n and string[right - left] == string[right]:
						right += 1
					z[i] = right - left
					right -= 1


class Solution:

	def search(self, pattern, text):

		def get_z_array(s):
			n = len(s)
			z = [0] * n
			(l, r) = (0, 0)
			for i in range(1, n):
				if i <= r:
					z[i] = min(r - i + 1, z[i - l])
				while i + z[i] < n and s[z[i]] == s[i + z[i]]:
					z[i] += 1
				if i + z[i] - 1 > r:
					(l, r) = (i, i + z[i] - 1)
			return z
		s = pattern + '$' + text
		z = get_z_array(s)
		(n, m) = (len(text), len(pattern))
		res = []
		for i in range(n + m + 1):
			if z[i] == m:
				res.append(i - m)
		return res


class Solution:

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


class Solution:

	def search(self, patt, s):
		pos = s.find(patt)
		z = []
		while pos >= 0:
			z.append(pos + 1)
			pos = s.find(patt, pos + 1)
		return z


class Solution:

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


class Solution:

	def search(self, patt, s):
		if not patt or not s:
			return

		def kmp(s):
			(pre_suf_len, table) = (0, [0])
			for i in range(1, len(s)):
				while pre_suf_len > 0 and s[i] != s[pre_suf_len]:
					pre_suf_len = table[pre_suf_len - 1]
				if s[i] == s[pre_suf_len]:
					pre_suf_len += 1
				table.append(pre_suf_len)
			return table
		n = len(s)
		ans = []
		table = kmp(s)
		i = 0
		j = 0
		while i < n:
			if i < n and patt[j] != s[i]:
				if j == 0:
					i += 1
				else:
					j = table[j - 1]
			else:
				i += 1
				j += 1
				if j == len(patt):
					ans.append(i - j + 1)
					j = table[j - 1]
		return ans


class Solution:

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


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


class Solution:

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


class Solution:

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


class Solution:

	def search(self, pat, text):
		tot = pat + '$' + text
		n = len(tot)
		z = [0] * n
		L = R = 0
		for i in range(1, n):
			if i > R:
				L = R = i
				while R < n and tot[R] == tot[R - L]:
					R += 1
				z[i] = R - L
				R -= 1
			else:
				k = i - L
				if z[k] < R - i + 1:
					z[i] = z[k]
				else:
					L = i
					while R < n and tot[R] == tot[R - L]:
						R += 1
					z[i] = R - L
					R -= 1
		res = []
		for i in range(n):
			if z[i] == len(pat):
				idx = i - len(pat) - 1
				res.append(idx + 1)
		return res


class Solution:

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


class Solution:

	def search(self, patt, s):
		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, patt, s):
		(l, r) = (0, 0)
		res = []
		while r < len(s):
			if r + 1 < len(patt):
				r += 1
			elif r + 1 >= len(patt):
				if s[l:r + 1] == patt:
					res.append(l + 1)
				l += 1
				r += 1
		return res if len(res) != 0 else [-1]


class Solution:

	def search(self, patt, s):
		new = ''
		for i in patt:
			new += i
		new += '$'
		for i in s:
			new += i
		z = self.calculateZ(new)
		result = []
		for i in range(len(z)):
			if z[i] == len(patt):
				result.append(i - len(patt))
		return result

	def calculateZ(self, input):
		z = [0 for i in range(len(input))]
		left = right = 0
		for k in range(1, len(input)):
			if k > right:
				left = right = k
				while right < len(input) and input[right] == input[right - left]:
					right += 1
				z[k] = right - left
				right -= 1
			else:
				k1 = k - left
				if z[k1] < right - k + 1:
					z[k] = z[k1]
				else:
					left = k
					while right < len(input) and input[right] == input[right - left]:
						right += 1
					z[k] = right - left
					right -= 1
		return z


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, patt, s):
		start = 0
		posl = list()
		pos = 0
		while True:
			pos = s.find(patt, start)
			if pos != -1:
				start = pos + 1
				posl.append(start)
			else:
				break
		return posl


class Solution:

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


class Solution:

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

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


class Solution:

	def search(self, patt, s):
		length = len(s)
		lis = []
		pos = s.find(patt)
		while pos >= 0:
			lis.append(pos + 1)
			pos = s.find(patt, pos + 1)
		return lis


class Solution:

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


class Solution:

	def search(self, patt, s):
		le = []
		k = 0
		while True:
			m = s.find(patt)
			if m != -1:
				s = s[m + 1:]
				a = m
				m = m + k
				k = a + k + 1
				le.append(m + 1)
			else:
				break
		return le


class Solution:

	def search(self, patt, s):
		z = []
		new = patt + '#' + s
		i = 0
		while i < len(new):
			while i <= len(patt):
				i += 1
			l = 0
			if new[l] == new[i]:
				r = i
				while r < len(new) and new[l] == new[r]:
					l += 1
					r += 1
			z.append(l)
			i += 1
		res = []
		for i in range(len(z)):
			if z[i] == len(patt):
				res.append(i + 1)
		return res


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def search(self, patt, s):
		s = patt + '$' + s
		n = len(s)
		z = [0] * n
		(l, r) = (0, 0)
		for i in range(1, n):
			if i > r:
				(l, r) = (i, i)
				while r < n and s[r - l] == s[r]:
					r += 1
				z[i] = r - l
				r -= 1
			else:
				k = i - l
				if z[k] < r - i + 1:
					z[i] = z[k]
				else:
					l = i
					while r < n and s[r - l] == s[r]:
						r += 1
					z[i] = r - l
					r -= 1
		out = []
		for i in range(len(z)):
			if z[i] == len(patt):
				out.append(i - len(patt))
		return out


class Solution:

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


class Solution:

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


class Solution:

	def search(self, patt, s):
		l = []
		c = 0
		p = s.find(patt, c)
		while p != -1:
			l.append(p + 1)
			p = s.find(patt, p + 1)
		if l == []:
			return [-1]
		return l


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def search(self, patt, s):
		res = []
		i = 0
		j = len(patt) - 1
		while i < len(s) - len(patt) + 1:
			if s[i:j + 1] == patt:
				res.append(i + 1)
			i += 1
			j += 1
		if len(res) > 0:
			return res
		return [-1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		patt = input().strip()
		ob = Solution()
		ans = ob.search(patt, s)
		if len(ans) == 0:
			print('-1', end=' ')
		else:
			for value in ans:
				print(value, end=' ')
		print()


def getZarr(string, z):
	n = len(string)
	(l, r, k) = (0, 0, 0)
	for i in range(1, n):
		if i > r:
			(l, r) = (i, i)
			while r < n and string[r - l] == string[r]:
				r += 1
			z[i] = r - l
			r -= 1
		else:
			k = i - l
			if z[k] < r - i + 1:
				z[i] = z[k]
			else:
				l = i
				while r < n and string[r - l] == string[r]:
					r += 1
				z[i] = r - l
				r -= 1

class Solution:

	def search(self, patt, s):
		concat = patt + '$' + s
		l = len(concat)
		res = []
		z = [0] * l
		getZarr(concat, z)
		for i in range(l):
			if z[i] == len(patt):
				res.append(i - len(patt))
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		patt = input().strip()
		ob = Solution()
		ans = ob.search(patt, s)
		if len(ans) == 0:
			print('-1', end=' ')
		else:
			for value in ans:
				print(value, end=' ')
		print()


class Solution:

	def search(self, patt, s):
		(m, n) = (len(patt), len(s))
		lps = [0] * m
		i = 1
		length = 0
		while i < m:
			if patt[i] == patt[length]:
				length += 1
				lps[i] = length
				i += 1
			elif length != 0:
				length = lps[length - 1]
			else:
				i += 1
		(i, j) = (0, 0)
		ans = []
		while i < n and j < m:
			if s[i] == patt[j]:
				i += 1
				j += 1
			if j == m:
				ans.append(i - j + 1)
				j = lps[j - 1]
			elif i < n and s[i] != patt[j]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		patt = input().strip()
		ob = Solution()
		ans = ob.search(patt, s)
		if len(ans) == 0:
			print('-1', end=' ')
		else:
			for value in ans:
				print(value, end=' ')
		print()


class Solution:

	def search(self, pat, txt):
		M = len(pat)
		N = len(txt)

		def computeLPSArray(pat, M, lps):
			len = 0
			lps[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
		lps = [0] * M
		j = 0
		computeLPSArray(pat, M, lps)
		ans = []
		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 = lps[j - 1]
			elif i < N and pat[j] != txt[i]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		s = input().strip()
		patt = input().strip()
		ob = Solution()
		ans = ob.search(patt, s)
		if len(ans) == 0:
			print('-1', end=' ')
		else:
			for value in ans:
				print(value, end=' ')
		print()