Given two strings A and B, you need to find the last occurrence ( 1 based indexing) of string B in string A.
 
Example 1:
Input:
A = abcdefghijklghifghsd
B = ghi
Output:
13
Explanation:
ghi occurs at position 13 for the
last time in string A.
Example 2:
Input:
A = abdbccaeab
B = abc
Output:
-1
Explanation:
abc is not a substring of A
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function findLastOccurence() which takes two strings A and B as input parameters and returns the position of the last occurrence of B in A. If B is not present in A, return -1.
 
Expected Time Complexity: O(len(A))
Expected Space Complexity: O(len(A))
 
Constarints:
1<=T<=100
1<=len(B)<=10^{5}
1<=len(A)<=10^{6}
len(A)>=len(B)

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:

    def findLastOccurence(self, A, B):

        # code here 

Solutions:
class Solution:

	def findLastOccurence(self, A, B):
		c = -1
		m = len(B)
		n = len(A)
		lps = [0] * m
		x = 1
		l = 0
		while x < m:
			if B[x] == B[l]:
				l += 1
				lps[x] = l
				x += 1
			elif l > 0:
				l = lps[l - 1]
			else:
				lps[x] = 0
				x += 1
		(i, j) = (0, 0)
		while n - i >= m - j:
			if B[j] == A[i]:
				i += 1
				j += 1
			if j == m:
				c = i - j
				j = lps[j - 1]
			elif i < n and B[j] != A[i]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
		if c == -1:
			return -1
		return c + 1


class Solution:

	def findLastOccurence(self, A, B):
		n = len(B)
		index = -1
		for i in range(len(A) - (n - 1)):
			if A[i:i + n] == B:
				index = i
		if index == -1:
			return -1
		else:
			return index + 1


class Solution:

	def findLastOccurence(self, A, B):
		a = len(A)
		b = len(B)
		val = -1
		for i in range(a):
			if A[i:i + b] == B:
				val = i + 1
		return val


class Solution:

	def findLastOccurence(self, A, B):
		n = len(B)
		maxi = -1
		for i in range(len(A) - n + 1):
			l = A[i:i + n]
			if l == B:
				maxi = max(i + 1, maxi)
		return maxi


class Solution:

	def findLastOccurence(self, A, B):
		op = A.rfind(B)
		if op >= 0:
			return op + 1
		else:
			return op


from typing import List

class Solution:

	def prefix(self, s: str) -> List[int]:
		res = [0] * len(s)
		i = 1
		j = 0
		while i < len(s):
			if s[i] == s[j]:
				j += 1
				res[i] = j
				i += 1
			elif j > 0:
				j = res[j - 1]
			else:
				res[i] = 0
				i += 1
		return res

	def findLastOccurence(self, s, p):
		sub = self.prefix(p)
		res = []
		(N, M) = (len(s), len(p))
		(i, j) = (0, 0)
		while i < N:
			if s[i] == p[j]:
				i += 1
				j += 1
				if j >= M:
					res.append(i - j + 1)
					j = sub[j - 1]
			elif j > 0:
				j = sub[j - 1]
			else:
				i += 1
		return res[-1] if len(res) else -1


class Solution:

	def findLastOccurence(self, A, B):
		lps = [0] * len(B)
		curr = 0
		for i in range(1, len(B)):
			while curr and B[i] != B[curr]:
				curr = lps[curr - 1]
			if B[i] == B[curr]:
				curr += 1
				lps[i] = curr
		ind_pattern = 0
		ans = -1
		for (i, ch) in enumerate(A):
			while ind_pattern and ch != B[ind_pattern]:
				ind_pattern = lps[ind_pattern - 1]
			if B[ind_pattern] == ch:
				if ind_pattern == len(B) - 1:
					ans = i - ind_pattern + 1
					ind_pattern = lps[ind_pattern]
				else:
					ind_pattern += 1
		return ans


class Solution:

	def findLastOccurence(self, A, B):
		A = A[::-1]
		B = B[::-1]
		if B in A:
			return len(A) - (A.index(B) + len(B)) + 1
		return -1


class Solution:

	def findLastOccurence(self, txt, pat):
		res = A.rfind(B)
		if res >= 0:
			return res + 1
		else:
			return res


class Solution:

	def findLastOccurence(self, A, B):
		i = A.rfind(B)
		return -1 if i == -1 else i + 1


def bad_char_preprocess(pat):
	if len(pat) < 2:
		return [[]]
	res = [[] for _ in range(len(pat) + 1)]
	check = [0 for _ in range(26)]
	for i in range(len(pat)):
		check[ord(pat[i]) - 97] = 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

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

def matched_prefix(pat):
	zsuf = z_box(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 len(preBad[pos]) > 0:
		return preBad[pos][ord(c) - 97]
	return 0

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

def get_suffix_shift(gs, mp, m, j):
	if gs[j + 1] > 0:
		stop = gs[j + 1]
		start = stop - m + j
		k = m + 1 - stop
	else:
		(start, stop) = (0, mp[j + 1] - 1)
		k = m - stop
	return (start, stop, k)

class Solution:

	def findLastOccurence(self, A, B):
		res = boyer_moore(B, A)
		if res == []:
			return -1
		return res[-1]


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

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

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

class Solution:

	def findLastOccurence(self, A, B):
		res = bad_char_shift(B, A)
		if res == []:
			return -1
		return res[-1]


class Solution:

	def findLastOccurence(self, A, B):

		def compute_lps(patt):
			lps = [0] * len(patt)
			(i, j) = (1, 0)
			while i < len(patt):
				if patt[i] == patt[j]:
					lps[i] = j + 1
					i += 1
					j += 1
				elif j != 0:
					j = lps[j - 1]
				else:
					i += 1
			return lps
		lps = compute_lps(B)
		i = j = 0
		last_indx = -1
		while i < len(A):
			if A[i] == B[j]:
				i += 1
				j += 1
			elif i < len(A) and A[i] != B[j]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
			if j == len(B):
				j = lps[j - 1]
				last_indx = i - len(B)
		return last_indx + 1 if last_indx != -1 else -1


class Solution:

	def findLastOccurence(self, A, B):
		n = len(A)
		m = len(B)
		lps = [0] * m
		self.computeLPS(B, lps, m)
		i = j = 0
		last_index = -1
		while i < n:
			if A[i] == B[j]:
				i += 1
				j += 1
			elif i < n and A[i] != B[j]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
			if j == m:
				last_index = i - m
				j = lps[j - 1]
		return last_index + 1 if last_index != -1 else -1

	def computeLPS(self, patt, lps, m):
		(i, j) = (1, 0)
		while i < len(patt):
			if patt[i] == patt[j]:
				lps[i] = j + 1
				i += 1
				j += 1
			elif j != 0:
				j = lps[j - 1]
			else:
				i += 1


class Solution:

	def extendedR(self, pattern):
		indices = [[] for i in range(26)]
		for i in range(len(pattern) - 1, -1, -1):
			indices[ord(pattern[i]) - ord('a')].append(i)
		return indices

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

	def N(self, string: str):
		rstring = string[::-1]
		rZ = self.Z(rstring)
		n = rZ[::-1]
		return n

	def Ldash(self, string: str):
		n = self.N(string)
		ld = [-1] * len(string)
		for i in range(0, len(string) - 1):
			j = len(string) - n[i]
			if j != len(string):
				ld[j] = i
		return ld

	def F(self, string: str):
		z_values = self.Z(string)
		f = [0] * len(string)
		f[0] = len(string)
		longest = 0
		for i in range(len(z_values) - 1, 0, -1):
			if z_values[i] == len(z_values) - i:
				longest = max(z_values[i], longest)
			f[i] = longest
		return f

	def bm_search(self, text: str, pattern: str):
		res = []
		r = self.extendedR(pattern)
		l = self.Ldash(pattern)
		mp = self.F(pattern)
		pt = len(pattern) - 1
		prev_pt = -1
		while pt < len(text):
			i = len(pattern) - 1
			j = pt
			while i > -1 and j > prev_pt and (pattern[i] == text[j]):
				i -= 1
				j -= 1
			if i == -1 or j == prev_pt:
				res.append(pt - len(pattern) + 1)
				if len(pattern) == 1:
					pt += 1
				else:
					pt += len(pattern) - mp[1]
			else:
				bchar_shift = 1
				for indx in r[ord(text[j]) - ord('a')]:
					if indx < i:
						bchar_shift = i - indx
						break
				if i + 1 == len(pattern):
					suffix_shift = 1
				elif l[i + 1] == -1:
					suffix_shift = len(pattern) - mp[i + 1]
				else:
					suffix_shift = len(pattern) - l[i + 1] - 1
				final_shift = max(bchar_shift, suffix_shift)
				if final_shift >= i + 1:
					prev_pt = pt
				pt += final_shift
		return res

	def findLastOccurence(self, A, B):
		matches = self.bm_search(A, B)
		if len(matches) == 0:
			return -1
		return matches[len(matches) - 1] + 1


class Solution:

	def findLastOccurence(self, A, B):
		(n, m) = (len(A), len(B))

		def z(string, pattern):

			def match(s, p):
				c = 0
				r = min(m - p, len(string) - s)
				for i in range(r):
					if pattern[p + i] != string[s + i]:
						break
					c += 1
				return c
			string = pattern + '$' + string
			Z = [0] * (n + m + 1)
			(l, r) = (0, 0)
			Z[1] = match(1, 0)
			if Z[1] != 0:
				l = 1
				r = Z[1]
			for i in range(2, n + m + 1):
				if i > r:
					Z[i] = match(i, 0)
					if Z[i] != 0:
						l = i
						r = i + Z[i] - 1
				else:
					prefixIndex = i - l
					if prefixIndex + Z[prefixIndex] - 1 < Z[l] - 1:
						Z[i] = Z[prefixIndex]
					elif prefixIndex + Z[prefixIndex] > r - l + 1:
						Z[i] = r - i + 1
					else:
						Z[i] = r - i + 1 + match(r + 1, r - i + 1)
						if Z[i] > r - i + 1:
							l = i
							r = i + Z[i] - 1
			return Z
		Z = z(A, B)
		for i in range(n + m, -1, -1):
			if Z[i] == m:
				return i - m
		return -1


class Solution:

	def findLastOccurence(self, A, B):

		def z(string, pattern):

			def matchlength(pos):
				c = 0
				for i in range(len(pattern)):
					if i >= len(pattern) or pos + i >= len(string):
						break
					if pattern[i] == string[pos + i]:
						c += 1
					else:
						break
				return c
			string = pattern + '$' + string
			Z = [0] * len(string)
			(l, r) = (0, 0)
			Z[1] = matchlength(1)
			if Z[1] != 0:
				l = 1
				r = Z[1]
			for i in range(2, len(string)):
				if i > r:
					Z[i] = matchlength(i)
					if Z[i] != 0:
						l = i
						r = i + Z[i] - 1
				else:
					prefixIndex = i - l
					if prefixIndex + Z[prefixIndex] - 1 < Z[l] - 1:
						Z[i] = Z[prefixIndex]
					else:
						m = r - i + 1
						Z[i] = m
						for j in range(len(pattern)):
							if r + 1 + j >= len(string) or m + j >= len(pattern):
								break
							if pattern[m + j] == string[r + 1 + j]:
								Z[i] += 1
							else:
								break
						l = i
						r = i + Z[i] - 1
			return Z
		Z = z(A, B)
		for i in range(len(A) + len(B), -1, -1):
			if Z[i] == len(B):
				return i - len(B)
		return -1


class Solution:

	def findLastOccurence(self, A, B):
		res = z_find(B, A)
		if res:
			return res[-1] + 1
		else:
			return -1

def z_alg(s: str):
	(l, r) = (0, 0)
	z = [-1]
	for k in range(1, len(s)):
		if k > r:
			i = 0
			while k + i < len(s) and s[i] == s[k + i]:
				i += 1
			if i:
				l = k
				r = k + i - 1
			z.append(i)
		else:
			z_k = z[k - l]
			width = r - k + 1
			if z_k < width:
				z.append(z_k)
			else:
				i = 0
				while r + 1 + i < len(s) and s[width + i] == s[r + 1 + i]:
					i += 1
				if i:
					l = k
					r = r + i
				z.append(width + i)
	return z

def z_find(pattern: str, search: str, divider: str='$'):
	res = []
	s = pattern + divider + search
	padding = len(pattern) + len(divider)
	z = z_alg(s)
	return [i for i in range(len(search)) if z[i + padding] >= len(pattern)]

def boyer_moore(pat: str, txt: str):
	n = len(txt)
	m = len(pat)
	bc = extended_bad_character_table(pat)
	gs = good_suffix(pat)
	mp = matched_prefix(pat)
	matched_indexes = []
	a = ord('a')
	(gblock, gr) = (0, -2)
	i = m - 1
	while i < n:
		j = 0
		while j < m and pat[m - j - 1] == txt[i - j]:
			j += 1
			if i - j == gr:
				j += gblock
		if j >= m:
			matched_indexes.append(i - m + 1)
			i += m - mp[1]
		else:
			bc_to = bc[m - j - 1][ord(txt[i - j]) - a]
			bc_jump = m - j - bc_to - 1 if bc_to > -1 else 1
			gs_to = gs[m - j]
			mp_to = mp[m - j]
			if gs_to == -1:
				gs_jump = m - mp_to
			else:
				gs_jump = m - gs_to - 1
			if bc_jump > gs_jump:
				gblock = 0
				i += bc_jump
			else:
				gr = i
				assert j >= 0
				gblock = j
				i += gs_jump
	return matched_indexes

def extended_bad_character_table(s: str):
	offset = ord('a')
	m = len(s)
	res = [[-1] * 26]
	for i in range(m - 1):
		char = ord(s[i]) - offset
		res.append([i if char == j else res[i][j] for j in range(26)])
	return res

def good_suffix(s: str):
	z_suffix = z_alg(s[::-1])
	m = len(s)
	gs = [-1] * (m + 1)
	for i in range(m - 1):
		gs[m - z_suffix[m - i - 1]] = i
	return gs

def good_suffix_but_two_loops(s: str):
	z_suffix = z_alg(s[::-1])[::-1]
	m = len(s)
	gs = [-1] * (m + 1)
	for i in range(m - 1):
		gs[m - z_suffix[i]] = i
	return gs

def matched_prefix(s: str):
	z = z_alg(s)
	m = len(s)
	res = [None] * m + [0]
	for i in range(m - 1, -1, -1):
		if i + z[i] == m:
			res[i] = z[i]
		else:
			res[i] = res[i + 1]
	return res


class Solution:

	def findLastOccurence(self, A, B):
		try:
			ind = A[::-1].index(B[::-1])
			return len(A) - ind - len(B) + 1
		except:
			return -1


from typing import List
from typing import Tuple
import sys

def z_algo(s: str) -> List[int]:
	z = [len(s)] + [0] * (len(s) - 1)
	(l, r) = (1, 1)
	for i in range(1, len(s)):
		(r, l) = max([(i, i), (r, l), (min(r, i + z[i - l] - 1), i)])
		while r < len(s) and s[r] == s[r - l]:
			r += 1
		z[i] = z[i - l] if l < i else r - l
	return z

def special_boyermoore(s: str, pat: str) -> List[int]:
	z_suffix = z_algo(pat[::-1])[::-1]
	good_suf = [-1] * (len(pat) + 1)
	match_pref = [-1] * (len(pat) + 1)
	for (i, k) in enumerate(z_suffix[:-1]):
		good_suf[k] = i
		match_pref[k] = match_pref[k] if -1 < i - k else i
	for i in range(1, len(match_pref)):
		match_pref[i] = max(match_pref[i], match_pref[i - 1])
	match_pref[len(pat)] = match_pref[len(pat) - 1]
	m_len = 0
	(l, r) = (0, 0)
	j = len(pat) - 1
	matches = []
	while j < len(s):
		while r < len(pat) - m_len and s[j - m_len] == pat[-(m_len + 1)]:
			m_len += 1
		if len(pat) - m_len == r:
			m_len += r - l
		while m_len < len(pat) and s[j - m_len] == pat[-(m_len + 1)]:
			m_len += 1
		if m_len == len(pat):
			matches.append(j - len(pat) + 1)
		if good_suf[m_len] == -1:
			j += len(pat) - match_pref[m_len] - 1
			(l, r) = (0, match_pref[m_len] + 1)
		else:
			j += len(pat) - good_suf[m_len] - 1
			(l, r) = (max(0, good_suf[m_len] - m_len + 1), good_suf[m_len] + 1)
		m_len = 0
	return matches

class Solution:

	def findLastOccurence(self, A, B):
		a = special_boyermoore(A, B)
		return -1 if not a else a[-1] + 1


class Solution:

	def findLastOccurence(self, txt, pat):
		lenTxt = len(txt)
		lenPat = len(pat)
		lps = Solution.computeLPSArray(pat)
		i = 0
		j = 0
		index = -1
		while lenTxt - i >= lenPat - j:
			if txt[i] == pat[j]:
				i += 1
				j += 1
			if j == lenPat:
				index = i - j + 1
				j = lps[j - 1]
			elif i < lenTxt and pat[j] != txt[i]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
		return index

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


class Solution:

	def findLastOccurence(self, A, B):
		if A == B:
			return 1
		ind = A.rfind(B)
		if ind == -1:
			return -1
		return ind + 1


class Solution:

	def findLastOccurence(self, A, B):
		n = len(A)
		m = len(B)
		res = -1
		for i in range(n - m + 1):
			if A[i:i + m] == B:
				res = i + 1
		return res


class Solution:

	def findLastOccurence(self, A, B):
		f = self.z_find(B, A)
		return -1 if not f else f[-1] + 1

	def z_alg(self, s: str):
		(l, r) = (0, 0)
		z = [-1]
		for k in range(1, len(s)):
			if k > r:
				i = 0
				while k + i < len(s) and s[i] == s[k + i]:
					i += 1
				if i:
					l = k
					r = k + i - 1
				z.append(i)
			else:
				z_k = z[k - l]
				width = r - k + 1
				if z_k < width:
					z.append(z_k)
				else:
					i = 0
					while r + 1 + i < len(s) and s[width + i] == s[r + 1 + i]:
						i += 1
					if i:
						l = k
						r = r + i
					z.append(width + i)
		return z

	def z_find(self, pattern: str, search: str, divider: str='$'):
		res = []
		s = pattern + divider + search
		padding = len(pattern) + len(divider)
		z = self.z_alg(s)
		return [i for i in range(len(search)) if z[i + padding] >= len(pattern)]


class Solution:

	def findLastOccurence(self, A, B):
		z_array = self.z(B + '$' + A)
		for i in range(len(z_array) - 1, -1, -1):
			if z_array[i] == len(B):
				return i - len(B)
		return -1

	def z(self, string):
		(l, r) = (-1, -1)
		z = [0] * len(string)
		for k in range(1, len(string)):
			if k > r:
				z[k] = self.compare(string, 0, k)
				(l, r) = (k, k + z[k] - 1)
			elif z[k - l] < r - k + 1:
				z[k] = z[k - l]
			elif z[k - l] == r - k + 1:
				z[k] = r - k + 1 + self.compare(string, r - k + 1, r + 1)
				(l, r) = (k, k + z[k] - 1)
			else:
				z[k] = r - k + 1
		return z

	def compare(self, string, j, k):
		i = 0
		while j + i < len(string) and k + i < len(string) and (string[j + i] == string[k + i]):
			i += 1
		return i


class Solution:

	def computeLps(self, pat, lps):
		lps[0] = 0
		m = len(pat)
		length = 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 findLastOccurence(self, A, B):
		res = -2
		(m, n) = (len(B), len(A))
		lps = [0] * m
		self.computeLps(B, lps)
		(i, j) = (0, 0)
		while n - i >= m - j:
			if A[i] == B[j]:
				i += 1
				j += 1
			if j == m:
				res = i - j
				j = lps[j - 1]
			elif i < n and A[i] != B[j]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
		return res + 1


class Solution:

	def findLastOccurence(self, A, B):
		n = len(A)
		m = len(B)
		for i in range(n - m, -1, -1):
			j = 0
			while j < m and A[i + j] == B[j]:
				j += 1
			if j == m:
				return i + 1
		return -1


class Solution:

	def findLastOccurence(self, A, B):

		def getLPSArray(pat, lps):
			lps[0] = 0
			M = len(pat)
			length = 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
		res = -2
		(M, N) = (len(B), len(A))
		lps = [0] * M
		getLPSArray(B, lps)
		(i, j) = (0, 0)
		while N - i >= M - j:
			if A[i] == B[j]:
				i += 1
				j += 1
			if j == M:
				res = i - j
				j = lps[j - 1]
			elif i < N and A[i] != B[j]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
		return res + 1


class Solution:

	def findLastOccurence(self, text, pat):
		n = len(pat)
		lsp = [0] * n
		prev = 0
		i = 1
		while i < n:
			if pat[i] == pat[prev]:
				prev += 1
				lsp[i] = prev
				i += 1
			elif prev == 0:
				lsp[i] = 0
				i += 1
			else:
				prev = lsp[prev - 1]
		(i, j) = (0, 0)
		ans = -2
		while i < len(text):
			if text[i] == pat[j]:
				i += 1
				j += 1
			elif j == 0:
				i += 1
			else:
				j = lsp[j - 1]
			if j == len(pat):
				ans = i - j
				j = lsp[j - 1]
		return ans + 1


class Solution:

	def findLastOccurence(self, text, pat):
		(rpat, rtext) = (pat[::-1], text[::-1])
		lsp = [0] * len(rpat)
		prev = 0
		for i in range(1, len(rpat)):
			if rpat[prev] == rpat[i]:
				prev += 1
				lsp[i] = prev
				i += 1
			elif prev == 0:
				lsp[i] = 0
				i += 1
			else:
				prev = lsp[prev - 1]
		(i, j) = (0, 0)
		while j < len(rtext):
			if rpat[i] == rtext[j]:
				i += 1
				j += 1
			elif i == 0:
				j += 1
			else:
				i = lsp[i - 1]
			if i == len(rpat):
				return len(text) - j + 1
		return -1


class Solution:

	def findLastOccurence(self, A, B):
		(n, m) = (len(A), len(B))
		lps = [0] * m
		l = 0
		i = 1
		while i < m:
			if B[i] == B[l]:
				l += 1
				lps[i] = l
				i += 1
			elif not l:
				lps[i] = 0
				i += 1
			else:
				l = lps[l - 1]
		(i, j) = (0, 0)
		last = -1
		while n - i >= m - j:
			if A[i] == B[j]:
				i += 1
				j += 1
			if j == m:
				last = i - j
				j = lps[j - 1]
			elif i < n and A[i] != B[j]:
				if j:
					j = lps[j - 1]
				else:
					i += 1
		return last + 1 if last != -1 else -1


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

class Solution:

	def findLastOccurence(self, A, B):
		n = len(A)
		res = []
		m = len(B)
		Lps = [0] * m
		lps(B, m, Lps)
		i = 0
		j = 0
		while i < n:
			if A[i] == B[j]:
				j += 1
				i += 1
			if j == m:
				res.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
		if len(res) == 0:
			return -1
		return res[-1]


def createTable(s: str):
	i = 0
	j = 1
	table = [0] * len(s)
	while j < len(s):
		if s[i] == s[j]:
			table[j] = i + 1
			i += 1
			j += 1
		elif i == 0:
			j += 1
		else:
			i = table[i - 1]
	return table

class Solution:

	def findLastOccurence(self, A, B):
		i = j = 0
		table = createTable(B)
		res = list()
		while i < len(A):
			if A[i] == B[j]:
				if j == len(B) - 1:
					res.append(i - j + 1)
					j = table[j]
				else:
					j += 1
				i += 1
			elif j == 0:
				i += 1
			else:
				j = table[j - 1]
		if len(res) == 0:
			return -1
		return res[len(res) - 1]


class Solution:

	def findLastOccurence(self, txt, pat):
		lps = self.generateLPS(pat)
		pat = '-' + pat
		(n, m, latestIndex) = (len(txt), len(pat) - 1, -1)
		i = j = 0
		while n - i >= m - j:
			if pat[j + 1] == txt[i]:
				i += 1
				j += 1
			elif j == 0:
				i += 1
			else:
				j = lps[j]
			if j == m:
				latestIndex = i - m + 1
				j = lps[j]
		return latestIndex

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


class Solution:

	def findLastOccurence(self, A, B):
		c = A.rfind(B)
		if c >= 0:
			return c + 1
		return c


class Solution:

	def findLastOccurence(self, s: str, pattern: str) -> bool:
		if len(pattern) == 0:
			return True
		if len(s) == 0:
			return True
		longestPrefixes = self.getLongestPrefixes(pattern)
		patternI = 0
		matches = []
		for i in range(len(s)):
			while True:
				if pattern[patternI] == s[i]:
					patternI = patternI + 1
					if patternI == len(pattern):
						matches.append(i - len(pattern) + 1)
						patternI = longestPrefixes[patternI - 1]
					break
				elif patternI > 0:
					patternI = longestPrefixes[patternI - 1]
				else:
					patternI = 0
					break
		if matches:
			return matches[-1] + 1
		else:
			return -1

	def getLongestPrefixes(self, pattern):
		ret = [0]
		for i in range(1, len(pattern)):
			if pattern[ret[-1]] == pattern[i]:
				ret.append(ret[-1] + 1)
				continue
			possible = ret[-1]
			while possible > 0:
				possible = ret[possible - 1]
				if pattern[possible] == pattern[i]:
					ret.append(possible + 1)
					break
			if len(ret) < i + 1:
				ret.append(1) if pattern[i] == pattern[0] else ret.append(0)
		return ret


class Solution:

	def get_lps(self, pat):
		n = len(pat)
		lps = [0 for i in range(n)]
		i = 1
		length = 0
		while i < n:
			if pat[i] == pat[length]:
				length += 1
				lps[i] = length
				i += 1
			elif length != 0:
				length = lps[length - 1]
				lps[i] = length
			else:
				i += 1
		return lps

	def findLastOccurence(self, A, B):
		(n, m) = (len(A), len(B))
		lps = self.get_lps(B)
		(i, j) = (0, 0)
		prev = -1
		while n - i >= m - j:
			if A[i] == B[j]:
				i += 1
				j += 1
			if j == m:
				prev = i - m + 1
				j = lps[j - 1]
			elif i < n and A[i] != B[j]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
		return prev


class Solution:

	def findLastOccurence(self, A, B):
		res = -1
		l = len(B)
		if B not in A:
			return -1
		for i in range(len(A) - l + 1):
			if B == A[i:i + l]:
				res = max(res, i)
		return res + 1


class Solution:

	def findLastOccurence(self, A, B):
		result = -1
		n = len(B)
		for i in range(len(A) - n + 1):
			if A[i:i + n] == B:
				result = i + 1
		return result


class Solution:

	def findLastOccurence(self, txt, pat):

		def funlps(s):
			arrlps = []
			arrlps.append(0)
			l = 0
			n = len(s)
			for i in range(1, n):
				if s[l] == s[i]:
					l += 1
					arrlps.append(l)
				else:
					while s[l] != s[i] and l > 0:
						l = arrlps[l - 1]
					if s[l] == s[i]:
						l += 1
						arrlps.append(l)
					if l == 0:
						arrlps.append(0)
			return arrlps
		lps = funlps(pat)
		N = len(txt)
		M = len(pat)
		i = 0
		j = 0
		ans = -1
		while N - i >= M - j:
			if pat[j] == txt[i]:
				i += 1
				j += 1
			if j == M:
				ans = 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


class Solution:

	def findLastOccurence(self, txt, pat):
		n = len(txt) - len(pat)
		ans = -1
		for i in range(n + 1):
			if txt[i:i + len(pat)] == pat:
				ans = i
		if ans == -1:
			return -1
		return ans + 1


def computeLPS(pattern):
	length = len(pattern)
	lps = [0 for _ in range(length)]
	index1 = 0
	index2 = 1
	while index2 < length:
		if pattern[index1] == pattern[index2]:
			index1 += 1
			lps[index2] = index1
			index2 += 1
		elif index1 != 0:
			index1 = lps[index1 - 1]
		else:
			lps[index2] = 0
			index2 += 1
	return lps

def search(text, pattern, lps):
	lengthText = len(text)
	lengthLPS = len(lps)
	indexText = 0
	indexLPS = 0
	lastMatchIndex = -1
	while lengthLPS - indexLPS <= lengthText - indexText:
		if text[indexText] == pattern[indexLPS]:
			indexText += 1
			indexLPS += 1
		elif indexLPS != 0:
			indexLPS = lps[indexLPS - 1]
		else:
			indexText += 1
		if indexLPS == lengthLPS:
			lastMatchIndex = indexText - indexLPS + 1
			indexLPS = lps[indexLPS - 1]
	return lastMatchIndex

class Solution:

	def findLastOccurence(self, text, pattern):
		return search(text, pattern, computeLPS(pattern))


class Solution:

	def findLastOccurence(self, A, B):
		LPS = [0] * len(B)
		(prevLPS, i) = (0, 1)
		while i < len(B):
			if B[i] == B[prevLPS]:
				LPS[i] = prevLPS + 1
				i += 1
				prevLPS += 1
			elif prevLPS == 0:
				LPS[i] = prevLPS
				i += 1
			else:
				prevLPS = LPS[prevLPS - 1]
		(i, j) = (0, 0)
		ans = -2
		while i < len(A):
			if A[i] == B[j]:
				i += 1
				j += 1
			elif j == 0:
				i += 1
			else:
				j = LPS[j - 1]
			if j == len(B):
				ans = i - len(B)
				j = 0
				if i != len(A) and len(B) != 1:
					i -= 1
		return ans + 1


class Solution:

	def findLastOccurence(self, A, B):
		n = len(A)
		m = len(B)
		lps = [0] * m

		def lps_array(B, lps, m):
			l = 0
			i = 1
			while i < m:
				if B[l] == B[i]:
					lps[i] = l + 1
					l += 1
					i += 1
				elif l != 0:
					l = lps[l - 1]
				else:
					lps[i] = 0
					i += 1
		lps_array(B, lps, m)
		ans = -1
		i = 0
		j = 0
		while n - i >= m - j:
			if A[i] == B[j]:
				i += 1
				j += 1
			if j == m:
				ans = max(ans, 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 ans


class Solution:

	def findLastOccurence(self, A, B):
		N = len(B)
		fallback = [-1] * N
		for i in range(1, N):
			(c, prev) = (B[i], fallback[i - 1])
			while prev >= 0 and c != B[prev + 1]:
				prev = fallback[prev]
			if B[prev + 1] == c:
				fallback[i] = prev + 1
		(res, pos) = (-1, -1)
		for (i, c) in enumerate(A):
			if pos == N - 1:
				pos = fallback[pos]
				while pos >= 0 and B[pos + 1] != c:
					pos = fallback[pos]
			else:
				while pos >= 0 and B[pos + 1] != c:
					pos = fallback[pos]
			if B[pos + 1] == c:
				pos += 1
			if pos == N - 1:
				res = i - N + 2
		return res


class Solution:

	def findLastOccurence(self, A, B):
		pos = -1
		for i in range(len(A) - len(B) + 1):
			if A[i:i + len(B)] == B:
				pos = i
		if pos != -1:
			pos += 1
		return pos


class Solution:

	def findLastOccurence(self, A, B):
		a = A[::-1]
		b = B[::-1]
		if b in a:
			c = a.index(b)
			return len(A) - c - len(b) + 1
		else:
			return -1


from typing import *

def lps_table(pat: List[int], M: int, lps: List[int]):
	i = 1
	leng = 0
	while i < M:
		if pat[i] == pat[leng]:
			leng += 1
			lps[i] = leng
			i += 1
		elif leng != 0:
			leng = lps[leng - 1]
		else:
			lps[i] = 0
			i += 1

class Solution:

	def findLastOccurence(self, txt, pat):
		lastIndex = -1
		M = len(pat)
		N = len(txt)
		lps = [0] * M
		lps_table(pat, M, lps)
		j = 0
		i = 0
		while N - i >= M - j:
			if pat[j] == txt[i]:
				i += 1
				j += 1
			if j == M:
				lastIndex = i - j
				j = lps[j - 1]
			elif i < N and pat[j] != txt[i]:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
		if lastIndex == -1:
			return -1
		return lastIndex + 1


class Solution:

	def findLastOccurence(self, A, B):
		ans = -2
		m = len(B)
		for i in range(len(A) - m + 1):
			if A[i:i + m] == B:
				ans = i
		return ans + 1


class Solution:

	def findLastOccurence(self, A, B):
		c = 0
		m = len(A)
		n = len(B)
		li = []
		pt = [0] * n
		self.preTablecalc(B, pt)
		i = 1
		j = 0
		while i <= m and j < n:
			c += 1
			if A[i - 1] == B[j]:
				j += 1
				i += 1
			if j == n:
				li.append(i - j)
				j = pt[j - 1]
			elif i <= m and A[i - 1] != B[j]:
				if j != 0:
					j = pt[j - 1]
				else:
					i += 1
		p = len(li)
		if p > 0:
			return li[p - 1]
		else:
			return -1

	def preTablecalc(self, B, pt):
		n = len(B)
		r = 0
		i = 1
		pt[0] = 0
		while i < n:
			if B[i] == B[r]:
				r += 1
				pt[i] = r
				i += 1
			elif r != 0:
				r = pt[r - 1]
			else:
				pt[i] = 0
				i += 1


class Solution:

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

	def findLastOccurence(self, A, B):
		m = len(A)
		n = len(B)
		last_occur = -1
		lps = [-1] * n
		self.computeLPS(B, lps)
		i = 0
		j = 0
		while i < m:
			if A[i] == B[j]:
				i += 1
				j += 1
			elif j != 0:
				j = lps[j - 1]
			else:
				i += 1
			if j == n:
				j = lps[j - 1]
				last_occur = i - n + 1
		return last_occur


class Solution:

	def findLastOccurence(self, A, B):
		m = len(A)
		n = len(B)
		l = []
		for i in range(m - n + 1):
			if A[i:i + n] == B:
				l.append(i + 1)
		if len(l) > 0:
			return max(l)
		else:
			return -1


class Solution:

	def findLastOccurence(self, A, B):
		ans = -1
		if A.__contains__(B):
			ans = A.rindex(B) + 1
		return ans


class Solution:

	def findLastOccurence(self, A, B):

		def KMPSearch(pat, txt):
			res = -1
			M = len(pat)
			N = len(txt)
			lps = [0] * M
			j = 0
			computeLPSArray(pat, M, lps)
			i = 0
			while N - i >= M - j:
				if pat[j] == txt[i]:
					i += 1
					j += 1
				if j == M:
					res = 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 res

		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
		return KMPSearch(B, A)


class Solution:

	def findLastOccurence(self, A, B):

		def zfunc(string):
			z = [0] * len(string)
			(l, r) = (0, 0)
			for i in range(1, len(string)):
				if i <= r:
					z[i] = min(z[i - l], r - i + 1)
				while i + z[i] < len(string) and string[i + z[i]] == string[z[i]]:
					z[i] += 1
				if i + z[i] - 1 > r:
					l = i
					r = i + z[i] - 1
			return z
		newstr = B + '$' + A
		ans = -1
		z = zfunc(newstr)
		for i in range(len(z)):
			if z[i] == len(B):
				ans = i - len(B)
		return ans


class Solution:

	def findLastOccurence(self, A, B):
		patLength = len(B)
		newString = B + '$' + A
		z = [0] * len(newString)
		for i in range(len(newString)):
			if i <= patLength:
				continue
			else:
				(left, right) = (0, 0)
				if newString[i] == newString[left]:
					right = i
					while right < len(newString) and newString[left] == newString[right]:
						right += 1
						left += 1
				z[i] = left
		ans = -1
		for i in range(len(z)):
			if z[i] == patLength:
				ans = i - patLength
		return ans


class Solution:

	def findLastOccurence(self, A, B):
		n = len(A)
		m = len(B)
		li = -2
		i = 0
		j = i + m
		while j <= n:
			if A[i:j] == B:
				li = i
			i += 1
			j += 1
		return li + 1


class Solution:

	def findLastOccurence(self, A, B):
		index = -1
		si = 0
		ei = len(B)
		while ei <= len(A):
			pat = A[si:ei]
			if pat == B:
				index = si
			si += 1
			ei += 1
		return index + 1 if index != -1 else -1


class Solution:

	def findLastOccurence(self, A, B):

		def findlps(lps, n, B):
			c = 0
			i = 1
			while i < n:
				if B[i] == B[c]:
					c += 1
					lps[i] = c
					i += 1
				elif c == 0:
					lps[i] = 0
					i += 1
				else:
					c = lps[c - 1]
		ans = [-1]
		m = len(A)
		n = len(B)
		lps = [0] * n
		findlps(lps, n, B)
		i = 0
		j = 0
		while m - i >= n - j:
			if A[i] == B[j]:
				i += 1
				j += 1
			if j == n:
				ans.append(i - j + 1)
				j = lps[j - 1]
			elif i < m and A[i] != B[j]:
				if j == 0:
					i += 1
				else:
					j = lps[j - 1]
		return ans[-1]


class Solution:

	def findLastOccurence(self, A, B):
		n = len(A)
		m = len(B)
		start_index = -1
		for index in range(n - m + 1):
			j = 0
			while j < m:
				if A[index + j] != B[j]:
					break
				j += 1
			if j == m:
				start_index = index + 1
		return start_index


class Solution:

	def findLastOccurence(self, A, B):
		if B in A:
			x = A.rfind(B)
			return x + 1
		else:
			return -1


class Solution:

	def findLastOccurence(self, A, B):
		lps = [0] * len(B)
		Len = 0
		i = 1
		while i < len(B):
			if B[i] == B[Len]:
				Len += 1
				lps[i] = Len
				i += 1
			elif Len != 0:
				Len = lps[Len - 1]
			else:
				i += 1
		i = 0
		j = 0
		last = -1
		while i < len(A):
			if A[i] == B[j]:
				i += 1
				j += 1
				if j == len(B):
					last = i - len(B) + 1
					j = lps[j - 1]
				continue
			if j != 0:
				j = lps[j - 1]
			else:
				i += 1
		return last


class Solution:

	def findLastOccurence(self, A, B):

		def find(B):
			n = len(B)
			lps = [0] * n
			i = 1
			lens = 0
			while i < n:
				if B[i] == B[lens]:
					lens += 1
					lps[i] = lens
					i += 1
				elif lens != 0:
					lens = lps[lens - 1]
				else:
					lps[i] = 0
					i += 1
			return lps
		lps = find(B)
		(i, j) = (0, 0)
		ans = -2
		while i < len(A) and j < len(B):
			if A[i] == B[j]:
				i += 1
				j += 1
			if j == len(B):
				if i - j > ans:
					ans = i - j
				j = lps[j - 1]
			elif i < len(A) and A[i] != B[j]:
				if j == 0:
					i += 1
				else:
					j = lps[j - 1]
		return ans + 1