Given two strings X and Y, the task is to find the last index in X at which string Y appears, if Y does not appear then the answer is -1. 
Example 1:
Input: X = "geeksforgeeks", Y = "geeks"
output: 9
Explanation: string "geeks" appears at 
index 1 and 9
Example 2:
Input: X = "geesforgees", Y = "geeks" 
output: -1 
Explanation: "geeks" does not appear
Your task:
You do not need to read any input or print anything. The task is to complete the function search(), which takes two strings as input and returns an integer. 
Expected Time Complexity: O(|X| + |Y|)
Expected Auxiliary Space: O(|X| + |Y|)
Constraints:
1 ≤ |X|, |Y| ≤ 10^{5}
Both the strings contains lower case English alphabets

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|X| + |Y|)
Expected Auxiliary Space: O(|X| + |Y|)

Starter code:
#User function Template for python3
class Solution:
	def search(self, X, Y):
		# code here

Solutions:
class Solution:

	def search(self, X, Y):
		if Y not in X:
			return -1
		else:
			return X.rfind(Y) + 1


class Solution:

	def search(self, X, Y):
		X = X[::-1]
		Y = Y[::-1]
		if Y not in X:
			return -1
		ind = X.index(Y)
		return len(X) - ind - len(Y) + 1


class Solution:

	def search(self, x, y):
		if y not in x:
			return -1
		else:
			return x.rfind(y) + 1


class Solution:

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


class Solution:

	def search(self, X, Y):
		X = X[::-1]
		if Y[::-1] in X:
			a = X.index(Y[::-1])
			return len(X) - len(Y) - a + 1
		else:
			return -1


class Solution:

	def search(self, X, Y):
		index = -1
		for i in range(len(X)):
			if i + len(Y) <= len(X) and X[i:i + len(Y)] == Y:
				index = i + 1
		return index


class Solution:

	def search(self, X, Y):
		n = len(Y)
		result = -1
		for i in range(len(X) - n + 1):
			if X[i:i + n] == Y:
				result = i + 1
		return result


class Solution:

	def search(self, X, Y):
		ans = -1
		i = 0
		j = len(X) - len(Y)
		while i <= j:
			if X[i:i + len(Y)] == Y:
				ans = i + 1
			i += 1
		return ans


class Solution:

	def search(self, X, Y):
		try:
			return X.rindex(Y) + 1
		except:
			return -1


class Solution:

	def search(self, X, Y):
		if Y not in X:
			return -1
		return X.rindex(Y) + 1


class Solution:

	def search(self, X, Y):
		n = len(Y)
		a = []
		for i in range(len(X)):
			if X[i:i + n] == Y:
				a.append(i + 1)
		if len(a) == 0:
			return -1
		return max(a)


class Solution:

	def search(self, X, Y):
		v = []
		for i in range(len(X)):
			if X[i] == Y[0]:
				if x[i:i + len(Y)] == Y:
					v.append(i + 1)
		if len(v) == 0:
			return -1
		return v[-1]


class Solution:

	def search(self, X, Y):
		idx = -1
		for i in range(len(X)):
			if Y in X[i:]:
				idx = i + 1
		return idx


class Solution:

	def search(self, X, Y):
		ans = X.rfind(Y)
		if ans == -1:
			return -1
		else:
			return ans + 1


class Solution:

	def search(self, X, Y):
		a = len(Y)
		z = []
		for i in range(len(X) - a + 1):
			temp = X[i:i + a]
			if temp == Y:
				z.append(i)
		if not z:
			return -1
		else:
			return z[len(z) - 1] + 1


class Solution:

	def search(self, x, y):
		k = x.rfind(y)
		if k == -1:
			return -1
		return k + 1


class Solution:

	def search(self, X, Y):
		if Y not in X:
			return -1
		else:
			res = []
			for x in range(len(X)):
				if Y in X[x:]:
					res.append(X[x:].index(Y) + (len(X) - len(X[x:])) + 1)
			return max(res)


class Solution:

	def search(self, X, Y):
		xx = X[::-1]
		yy = Y[::-1]
		if yy in xx:
			return len(X) - (xx.index(yy) + len(yy) - 1)
		else:
			return -1


class Solution:

	def search(self, X, Y):
		if X.rfind(Y) >= 0:
			return X.rfind(Y) + 1
		return -1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(x, y) = input().split()
		ob = Solution()
		answer = ob.search(x, y)
		print(answer)


class Solution:

	def search(self, X, Y):
		newX = X[::-1]
		newY = Y[::-1]
		if newX.find(newY) == -1:
			return -1
		return len(X) - (newX.find(newY) + len(Y) - 1)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(x, y) = input().split()
		ob = Solution()
		answer = ob.search(x, y)
		print(answer)


class Solution:

	def search(self, X, Y):
		Y = Y[::-1]
		X = X[::-1]
		if X.count(Y) == 0:
			return -1
		try:
			d = X.find(Y)
			return len(X) - len(Y) - d + 1
		except:
			return -1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(x, y) = input().split()
		ob = Solution()
		answer = ob.search(x, y)
		print(answer)


class Solution:

	def search(self, X, Y):
		n = len(Y) - 1
		c = 0
		for i in range(len(X) - 1, -1, -1):
			if Y[n] == X[i]:
				c += 1
				while n:
					n -= 1
					i -= 1
					if Y[n] != X[i]:
						break
					c += 1
				if c == len(Y):
					return i + 1
				n = len(Y) - 1
				c = 0
		return -1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(x, y) = input().split()
		ob = Solution()
		answer = ob.search(x, y)
		print(answer)


class Solution:

	def search(self, X, Y):
		if Y not in X:
			return -1
		else:
			return X.rindex(Y) + 1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(x, y) = input().split()
		ob = Solution()
		answer = ob.search(x, y)
		print(answer)


class Solution:

	def search(self, X, Y):
		a = len(X)
		b = len(Y)
		r = 0
		for i in range(a):
			if X[i:i + b] == Y:
				r = i + 1
		if r > 0:
			return r
		else:
			return -1


class Solution:

	def search(self, X, Y):
		ans = -1
		m = len(Y)
		for i in range(len(X) - m + 1):
			if X[i:i + m] == Y:
				ans = i + 1
		return ans


class Solution:

	def search(self, X, Y):
		X = X[::-1]
		Y = Y[::-1]
		n = len(X)
		i = X.find(Y)
		if i == -1:
			return -1
		return n - (i + len(Y) - 1)


class Solution:

	def search(self, x, y):
		n1 = len(x)
		n2 = len(y)
		firstchar = y[0]
		for i in range(n1 - 1, -(n1 + 1), -1):
			if x[i] == firstchar:
				if x[i:i + n2] == y:
					return i + 1
		return -1


class Solution:

	def search(self, x, y):
		ind = x.rfind(y)
		if ind == -1:
			return -1
		else:
			return ind + 1


class Solution:

	def search(self, X, Y):
		c = 0
		i = 0
		j = int(len(y) - 1)
		ans = []
		while j < len(X):
			if X[i:j + 1] == Y:
				ans.append(i + 1)
				c = c + 1
			i = i + 1
			j = j + 1
		if c == 0:
			return -1
		return ans[-1]


class Solution:

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

	def search(self, X, Y):
		LPSArr = self.lps(Y)
		(i, j, lenX) = (0, 0, len(X))
		(count, pos) = (0, -1)
		while j < lenX:
			if X[j] == Y[i]:
				i += 1
				j += 1
			elif i == 0:
				j += 1
			else:
				i = LPSArr[i - 1]
			if i == len(Y):
				count += 1
				pos = j - len(Y) + 1
				i = LPSArr[i - 1]
		return pos