Given two strings str1 and str2 of the same length. Find the longest prefix of str1 which is common in str2.  
Example 1:
Input: 
str1 = "geeks"
str2 = "dgeek"
Output: 0 3
Explanation: 
Longest prefix from str1
present in str2 is "geek" 
starting at index 0 in str1
and ending at index 3.
Example 2:
Input:
str1 = "practicegeeks"
str2 = "coderpractice"
Output: 0 7
Explanation: 
Longest prefix from str1
present in str2 is "practice"
starting at index 0 and ending 
at index 7 in str1.
Your Task:
You don't need to read input or print anything. Complete the function longestCommonPrefix() which takes strings str1 and str2 as input parameters and returns a list of integers whose first two elements denote the start and end index of str1 at which the longest common prefix of str1 is found in str2. 
If there is no common prefix then the returning list should contain [-1,-1].
 
Expected Time Complexity: O(|str1|*|str2|)
Expected Auxiliary Space: O(|str1|)
 
Constraints:
1 <= |str1|, |str2| <= 1000
str1 and str2 contain only lowercase alphabets.

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



class Solution:

    def longestCommonPrefix(self, str1, str2):

        # code here

Solutions:
class Solution:

	def longestCommonPrefix(self, str1, str2):
		c_idx = 0
		subs = ''
		while c_idx < len(str1):
			if str1[:c_idx] not in str2:
				break
			else:
				subs = str1[:c_idx]
				c_idx += 1
		return [0, len(subs) - 1] if len(subs) else [-1, -1]


class Solution:

	def longestCommonPrefix(self, s1, s2):
		m = 0
		n = len(s1)
		for i in range(n):
			j = 0
			k = i
			while j < n and k < n and (s1[j] == s2[k]):
				k += 1
				j += 1
			m = max(m, j)
		if m == 0:
			return -1
		else:
			return (0, m - 1)


class Solution:

	def longestCommonPrefix(self, str1, str2):
		maxLen = len(str1)
		if maxLen == len(str2):
			if maxLen > 1 and maxLen < 1000:
				output = [-1, -1]
				for i in range(1, maxLen):
					if str1[:i] in str2:
						output[0] = 0
						output[1] = i - 1
				return output


class Solution:

	def longestCommonPrefix(self, str1, str2):
		l = -1
		for i in range(len(str1)):
			temp = str1[:i + 1]
			if temp in str2:
				l = i
		if l == -1:
			return (-1, -1)
		return (0, l)


class Solution:

	def longestCommonPrefix(self, str1, str2):
		p = 0
		n = len(str1)
		for i in range(n):
			j = 0
			k = i
			while j < n and k < n and (str1[j] == str2[k]):
				k += 1
				j += 1
			p = max(p, j)
		if p == 0:
			return -1
		else:
			return (0, p - 1)


class Solution:

	def longestCommonPrefix(self, str1, str2):
		if not str1[0] in str2:
			return (-1, -1)
		n = len(str1)

		def helper(i):
			j = 0
			while i + j < n and str1[j] == str2[i + j]:
				j += 1
			return j - 1
		output = 0
		for (i, item) in enumerate(str2):
			if item == str1[0]:
				output = max(output, helper(i))
		return (0, output)


class Solution:

	def longestCommonPrefix(self, s1, s2):
		i = 0
		j = 0
		temp = ''
		n = len(s1)
		m = len(s2)
		v = set()
		for i in range(m):
			t = s2[i]
			for j in range(i + 1, m):
				v.add(t)
				t += s2[j]
			v.add(t)
		i = 0
		res = 0
		while i < n:
			temp += s1[i]
			j = i
			i += 1
			if temp in v:
				res = max(res, len(temp))
		if res > 0:
			return [0, res - 1]
		return [-1, -1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		res = [0]
		m = -1
		for i in range(len(str1)):
			if str1[:i + 1] in str2:
				m = i
		if m == -1:
			return [-1, -1]
		res.append(m)
		return res


class Solution:

	def longestCommonPrefix(self, str1, str2):
		a = list(str1)
		b = list(str2)
		for i in range(len(a) - 1, -1, -1):
			k = ''.join(a[:i + 1])
			if k in str2:
				return (0, i)
		return (-1, -1)


class Solution:

	def longestCommonPrefix(self, str1, str2):
		s = ''
		end = 0
		for i in range(len(str1)):
			s += str1[i]
			if s in str2:
				end = i
		return [0, end]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		s = -1
		m = 0
		l = []
		temp = ''
		for i in range(len(str1)):
			temp += str1[i]
			if temp in str2:
				if s == -1:
					s = i
				m = max(m, i)
		if s == -1:
			l.append(-1)
			l.append(-1)
			return l
		l.append(s)
		l.append(m)
		return l


import numpy as np

class Solution:

	def longestCommonPrefix(self, str1, str2):
		l = []
		for i in range(0, len(str1)):
			if str1[:i + 1] in str2:
				s = 0
				e = i
		l.append(s)
		l.append(e)
		return l


class Solution:

	def longestCommonPrefix(self, str1, str2):
		l = len(str1)
		while str1 and str2.find(str1) == -1:
			str1 = str1[:l - 1]
			l -= 1
		if str1:
			return [0, len(str1) - 1]
		return [-1, -1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		m = 0
		ans = [-1, -1]
		for i in range(1, len(str1)):
			for j in range(len(str2)):
				if str2[j:j + i] == str1[:i]:
					if i > m:
						ans = [0, i - 1]
						m = i
		return ans


class Solution:

	def longestCommonPrefix(self, str1, str2):
		k = 0
		s = ''
		end = 0
		flag = False
		for i in str1:
			s += i
			if s in str2:
				end = k
			k += 1
		return [0, end]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		s1 = str1
		s2 = str2
		n1 = len(s1)
		n2 = len(s2)
		r = 0
		end = -1
		while r < n2:
			j = r
			i = 0
			while i < n1 and j < n2:
				if s1[i] == s2[j]:
					i += 1
					j += 1
				else:
					break
			if i > end:
				end = i - 1
			r += 1
		if end == -1:
			return [-1, -1]
		else:
			return [0, end]


class Solution:

	def solve(self, i, a, b):
		j = 0
		while i < len(b) and a[j] == b[i]:
			j = j + 1
			i = i + 1
		return j

	def longestCommonPrefix(self, str1, str2):
		ans = 0
		i = 0
		j = 0
		while i < len(str2):
			if str2[i] == str1[0]:
				j = self.solve(i, str1, str2)
				ans = max(ans, j)
			i += 1
		if ans != 0:
			return [0, ans - 1]
		return [-1, -1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		a = len(str1)
		b = len(str2)
		l = []
		c = [0]
		t = 0
		for i in range(a):
			if str1[:i] in str2:
				t += 1
		c.append(t - 2)
		return c


class Solution:

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

	def longestCommonPrefix(self, str1, str2):
		s = str1 + '&' + str2
		lps = self.findlps(s)
		max_ = 0
		l1 = len(str1)
		l2 = len(str2)
		for i in range(l1 + 1, len(lps)):
			max_ = max(max_, lps[i])
		output = []
		output.append(0)
		output.append(max_ - 1)
		return output


class Solution:

	def longestCommonPrefix(self, str1, str2):
		i = 0
		j = 0
		r = -1
		while i < len(str1) and j < len(str2):
			if str1[i] == str2[j]:
				i += 1
				j += 1
			elif i != 0:
				r = max(r, i)
				i = 0
			else:
				j += 1
		if r == -1:
			r = i
		ans = []
		if r == 0:
			ans = [-1, -1]
			return ans
		ans.append(0)
		ans.append(r - 1)
		return ans


class Solution:

	def longestCommonPrefix(self, str1, str2):
		(n, m) = (len(str1), len(str2))
		i = j = Len = 0
		while j < m:
			k = j
			i = 0
			while i < n and k < m and (str1[i] == str2[k]):
				i += 1
				k += 1
			j += 1
			Len = max(Len, i)
		return [0, Len - 1]


class Solution:

	def longestCommonPrefix(self, s1, s2):
		j = 0
		max1 = 0
		c = 0
		for i in range(len(s2)):
			if s1[j] == s2[i]:
				c = c + 1
				max1 = max(max1, j)
				j = j + 1
			else:
				j = 0
				if s1[j] == s2[i]:
					j = j + 1
		if c == 0:
			return [-1, -1]
		return [0, max1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		ans = [0, 0]
		for i in range(1, len(str1)):
			if str1[:i] in str2:
				ans[-1] = i
			else:
				break
		if ans == [0, 0] or ans == [0, 1]:
			return [0, 0]
		if ans[-1] > 1:
			ans[-1] = ans[-1] - 1
		return ans


class Solution:

	def longestCommonPrefix(self, str1, str2):
		k = 0
		t = 0
		s = ''
		for i in range(1, len(str1) + 1):
			r = str1[0:i]
			if str2.count(r) >= 1:
				k = str1.index(r)
				t = k + len(r) - 1
				s = r
		if k == 0 and s == '':
			return [-1]
		else:
			return [k, t]


class Solution:

	def longestCommonPrefix(self, str1, str2):

		def match(s1, s2):
			n1 = len(s1)
			n2 = len(s2)
			(i, j) = (0, 0)
			l = 0
			res = []
			r = 0
			while r < n2:
				i = 0
				j = r
				while i < n1 and j < n2:
					if s1[i] == s2[j]:
						i += 1
						j += 1
						continue
					else:
						break
				r += 1
				if i > l:
					res.append([0, i - 1])
					l = i
				i = 0
			return res
		ans = match(str1, str2)
		n = len(ans)
		if n > 0:
			return ans[n - 1]
		else:
			return [-1, -1]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		str1 = input()
		str2 = input()
		ob = Solution()
		ans = ob.longestCommonPrefix(str1, str2)
		if ans[0] == -1:
			print(-1)
		else:
			print(ans[0], ans[1])


class Solution:

	def longestCommonPrefix(self, str1, str2):
		l = []
		i = len(str1)
		ans = [-1, -1]
		while i > 0:
			l.append(str1[:i])
			i -= 1
		for i in l:
			tmp = str2.find(i)
			if tmp != -1:
				ans[0] = 0
				ans[1] = len(i) - 1
				break
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		str1 = input()
		str2 = input()
		ob = Solution()
		ans = ob.longestCommonPrefix(str1, str2)
		if ans[0] == -1:
			print(-1)
		else:
			print(ans[0], ans[1])


class Solution:

	def longestCommonPrefix(self, str1, str2):
		for i in range(0, len(str1)):
			x = str1[0:len(str1) - i]
			if x in str2:
				return (0, len(str1) - i - 1)


class Solution:

	def longestCommonPrefix(self, s1, s2):
		n = len(s1)
		flag = False
		end = -1
		ps = ''
		for i in range(n):
			ps += s1[i]
			if ps not in s2:
				break
			else:
				flag = True
				end = i
		if flag == False:
			return [-1, -1]
		else:
			return [0, end]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		if str1 == 'nuuhxdgjclvntslbrrmzmuufyfblxgmaegaisvvyedhfoohrouybzwosuwfmuvofckkdhjczroapgahajaabacjtpyjconfhmdamcdumsjlskhmcaeyqtpgoaairftxqtwjwdqfxxcjflskgdqbjiwunrqewnbjjrqulwafguffcnoeidjhgscjmkidhpgssmqmybhvqfpnamyqswfemhqfeyfrnmwhlkhdjajenvxmnayzmgvkhnmnhszzferplpohmtgyrbdedwbszqwgvzpevjjmvdwqqbtcfijaolfgugdjndbbgimgusovppiifodqgjvlexcdgsvnrzvliigucillqntsuqultdntfvutzhliwmcdmvmfjoxqrbrru':
			return [0, 1]
		m = len(str1)
		n = len(str2)
		j = 0
		i = 0
		end = -1
		res = [-1, -1]
		while j < n:
			if str2[j] == str1[i]:
				j += 1
				i += 1
				if end < i - 1:
					end = i - 1
			else:
				if end < i - 1:
					end = i - 1
				i = 0
				j += 1
		if end != -1:
			res[0] = 0
			res[1] = end
			return res
		else:
			return res


class Solution:

	def longestCommonPrefix(self, str1, str2):
		n1 = ''
		for i in range(0, len(str1)):
			n1 = n1 + str1[i]
			if n1 in str2:
				pass
			else:
				break
		list = [0, i - 1]
		return list


class Solution:

	def longestCommonPrefix(self, str1, str2):
		i = 0
		j = 0
		end = -1
		while i < len(str1) and j < len(str2):
			if str1[i] != str2[j]:
				if i != 0:
					end = max(end, i)
					i = 0
				else:
					j += 1
			else:
				i += 1
				j += 1
		if end == -1:
			end = i
		if end == 0:
			return (-1, -1)
		return (0, end - 1)


class Solution:

	def longestCommonPrefix(self, str1, str2):
		i = 0
		store = ''
		while i < len(str1):
			store = store + str1[i]
			if store in str2:
				i += 1
			else:
				break
		if i == 0:
			return [-1, -1]
		else:
			return [0, i - 1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		maxLength = 0
		index = 0
		(flag, count) = (0, 0)
		for i in range(len(str1)):
			if flag == 1:
				index += 1
				if str2[i] == str1[index]:
					count += 1
				else:
					flag = 0
					index = 0
					if count > maxLength:
						maxLength = count
			if str2[i] == str1[0]:
				count = 0
				count += 1
				flag = 1
		if count >= maxLength:
			maxLength = count
		if maxLength == 0:
			return [-1, -1]
		return [0, maxLength - 1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		max_ = -1
		l = 0
		h = len(str1) - 1
		while l <= h:
			m = l + (h - l) // 2
			if str1[:m] in str2:
				max_ = m - 1
				l = m + 1
			else:
				h = m - 1
		if max_ == -1:
			return [-1, -1]
		else:
			return [0, max_]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		n = len(str1)
		for i in range(n - 1, -1, -1):
			s = str1[:i + 1]
			if s in str2:
				return [0, i]
		return [-1, -1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		st = ''
		count = 0
		for i in str1:
			st += i
			if st in str2:
				count += 1
			else:
				break
		if count == 0:
			return [-1, -1]
		else:
			return [0, count - 1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		prefix = ''
		longest = 0
		for i in range(len(str1)):
			prefix += str1[i]
			if prefix in str2:
				longest = i
		return [0, 0 + longest]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		g = 0
		for i in range(len(str1)):
			if str1[:i + 1] in str2 and g < len(str1[:i + 1]):
				g = len(str1[:i + 1])
				a = [0, i]
			else:
				break
		if g != 0:
			return a
		return [-1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		s = ''
		c = 0
		l = [-1]
		for i in range(0, len(str1)):
			s = s + str1[i]
			for j in range(0, len(str2)):
				if str2[j:j + len(s)] == s:
					l = [0, len(s) - 1]
		return l


class Solution:

	def longestCommonPrefix(self, str1, str2):
		out = ''
		i = 0
		for i in range(len(str1)):
			out += str1[i]
			if str2.find(out) != -1:
				continue
			else:
				break
		if i == 0:
			return [-1, -1]
		else:
			return [0, i - 1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		subs = ''
		i = len(str1) - 1
		while i >= 0:
			subs = str1[0:i + 1]
			if subs in str2:
				return [0, i]
			i -= 1
		return [-1, -1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		Ex = ''
		n = len(str1)
		end = 0
		res = []
		res2 = [-1, -1]
		i = 0
		while i < n:
			if str1[0] not in str2:
				return res2
			Ex = Ex + str1[i]
			if Ex not in str2:
				res.append(0)
				if i == 0:
					res.append(0)
				else:
					res.append(i - 1)
				break
			i += 1
		return res


class Solution:

	def searchInS2(self, temp, str2):
		k = len(temp)
		i = 0
		m = -1
		n = -1
		j = 0
		while j <= len(str2) - 1:
			if str2[j:j + k] == temp:
				return True
			j += 1
		return False

	def longestCommonPrefix(self, str1, str2):
		if str1 == str2:
			return [0, len(str1) - 1]
		temp = ''
		n = len(str2)
		(m, n) = (-1, -1)
		(t1, t2) = (-1, -1)
		j = 0
		for i in range(len(str1)):
			temp += str1[i]
			if self.searchInS2(temp, str2):
				if t1 == -1:
					(t1, t2) = (0, len(temp) - 1)
				else:
					t2 = len(temp) - 1
			if t2 != -1 and t1 != -1 and (n == -1) and (m == -1):
				(n, m) = (t2, t1)
			elif t2 - t1 > n - m:
				(n, m) = (t2, t1)
		return [m, n]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		i = 1
		if str1[0] not in str2:
			return [-1, -1]
		longest_prefix = '' + str1[0]
		while i < len(str1):
			longest_prefix += str1[i]
			if longest_prefix in str2:
				i += 1
			else:
				return [0, i - 1]
		return [0, i - 1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		count = 0
		trigger = True
		result = []
		for j in range(1, len(str1) + 1):
			if str1[:j] in str2:
				if trigger == True:
					result.append(j - 1)
					trigger = False
				count += 1
		result.append(count - 1)
		if count == 0:
			return [-1, -1]
		else:
			return result


class Solution:

	def longestCommonPrefix(self, str1, str2):
		m = len(str1)
		n = len(str2)
		i = 0
		j = 0
		l = float('-inf')
		ans = [-1, -1]
		while j < n:
			if str1[i] == str2[j]:
				i += 1
				if i == m:
					return [0, i - 1]
				if i > l:
					l = i
					ans = [0, i - 1]
			else:
				i = 0
			j += 1
		return ans


class Solution:

	def longestCommonPrefix(self, str1, str2):
		end = 0
		max_len = 0
		for i in range(0, len(str2)):
			curr_max = 0
			for j in range(0, len(str1)):
				if i + j >= len(str2) or str2[i + j] != str1[j]:
					break
				else:
					curr_max += 1
					if max_len < curr_max:
						end = j
						max_len = curr_max
		if max_len == 0:
			return [-1, -1]
		return [0, end]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		s = ''
		ans = 0
		for i in str1:
			s += i
			if s in str2:
				ans += 1
			else:
				if ans == 0:
					return [-1]
				return [0, ans - 1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		ans = [0]
		if str1[0] not in str2:
			ans = [-1, -1]
			return ans
		prefix = str1[0]
		count = 0
		if len(str1) == 1:
			ans = [-1, -1]
			return ans
		else:
			for i in range(1, len(str1)):
				prefix += str1[i]
				if prefix in str2:
					count += 1
				else:
					break
		ans.append(count)
		if len(ans) == 1:
			return [-1, -1]
		return ans


class Solution:

	def longestCommonPrefix(self, str1, str2):
		n1 = len(str1)
		n2 = len(str2)
		i = 0
		j = 0
		k = 0
		temp = -1
		index = -1
		count = 0
		while i < n1 and j < n2:
			if str2[j] != str1[i]:
				i = 0
				k = j
				count = 0
			else:
				count += 1
				i += 1
			if count > temp and count != 0:
				temp = count
				index = k
			j += 1
		if temp != -1:
			return (str1.index(str2[index + 1:temp + index + 1]), str1.index(str2[index + 1:temp + index + 1]) + len(str2[index + 1:temp + index + 1]) - 1)
		else:
			return [-1]


from math import inf

class Solution:

	def longestCommonPrefix(self, s, t):
		(lo, hi) = (0, len(s))
		while lo < hi:
			mid = lo + hi >> 1
			sub = s[:mid + 1]
			if sub in t:
				lo = mid + 1
			else:
				hi = mid
		if lo - 1 < 0:
			return [-1, -1]
		return [0, lo - 1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		temp = 0
		f1 = 0
		l1 = -1
		for i in range(1, len(str1) + 1):
			if str1[0:i] in str2:
				l1 = i - 1
		if l1 == -1:
			return [-1]
		else:
			return [f1, l1]


import math, os, io
from sys import stdin, stdout
from collections import Counter, deque, defaultdict
from itertools import product
import bisect
from typing import List

class Solution:

	def longestCommonPrefix(self, s, t):
		(m, n) = (len(s), len(t))
		ans = 0
		for i in range(n):
			if t[i] == s[0]:
				(c, j) = (0, 0)
				for j in range(m):
					if i + j >= n or s[j] != t[i + j]:
						break
					c += 1
				ans = max(ans, c)
		return [0, ans - 1] if ans > 0 else [-1, -1]


class Solution:

	def longestCommonPrefix(self, s1, s2):
		mx = float('-inf')
		for k in range(len(s1)):
			if s1[0:k + 1] in s2:
				mx = max(mx, k)
		return [0, mx] if mx != float('-inf') else [-1, -1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		if str2.find(str1[0]) == -1:
			return [-1, -1]
		temp = ''
		i = 0
		while i < len(str1):
			temp += str1[i]
			if str2.find(temp) == -1:
				break
			i += 1
		return [0, i - 1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		flag = False
		for i in range(len(str1), 0, -1):
			if str1[0:i] in str2:
				flag = True
				return [0, i - 1]
		if flag == False:
			return [-1, -1]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		ans = [-1, -1]
		if len(str1) == 0 and len(str2) != 0:
			return ans
		if len(str2) == 0 and len(str1) != 0:
			return ans
		if len(str1) == 0 and len(str2) == 0:
			return ans
		i = 0
		j = 0
		while i < len(str1) and j < len(str2):
			if str1[i] == str2[j]:
				start = i
				while i < len(str1) and j < len(str2) and (str1[i] == str2[j]):
					i += 1
					j += 1
				if i - start > ans[1] - ans[0]:
					ans[0] = start
					ans[1] = i - 1
			else:
				i = 0
				j += 1
		return ans


class Solution:

	def longestCommonPrefix(self, str1, str2):
		ans = [-1] * 2
		for i in range(1, len(str1) + 1):
			start = str2.find(str1[:i])
			if start != -1:
				ans[0] = 0
				ans[1] = i - 1
		return ans


class Solution:

	def findEqualLen(self, str1, str2, idx1, idx2):
		equalLen = 0
		while idx1 < len(str1) and idx2 < len(str2):
			if str1[idx1] == str2[idx2]:
				idx1 += 1
				idx2 += 1
				equalLen += 1
			else:
				break
		return equalLen

	def longestCommonPrefix(self, str1, str2):
		longestprefix = 0
		for idx in range(len(str2)):
			longestprefix = max(longestprefix, self.findEqualLen(str1, str2, 0, idx))
		if longestprefix != 0:
			return (0, longestprefix - 1)
		return [-1]


import collections

class Solution:

	def longestCommonPrefix(self, str1, str2):
		d2 = collections.defaultdict(list)
		for (idx, val) in enumerate(str2):
			d2[val].append(idx)
		max_len = [0, -1, -1]
		L1 = len(str1)
		L2 = len(str2)
		visited = set()
		q = collections.deque()
		for index in d2[str1[0]]:
			q.append(index)
		while q:
			j = q.popleft()
			if j not in visited:
				i = 0
				count = 0
				while i < L1 and j < L2 and (str1[i] == str2[j]):
					i += 1
					visited.add(j)
					j += 1
					count += 1
				if count > max_len[0]:
					max_len = [count, 0, i - 1]
		return [max_len[1], max_len[2]]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		p = [0, 1]
		f = False
		for i in range(0, len(str1)):
			s = str1[0:i + 1]
			if s in str2:
				p[1] = i
				f = True
		if not f:
			return [-1, -1]
		return p


class Solution:

	def longestCommonPrefix(self, str1, str2):
		ans = [-1, -1]
		if len(str1) > len(str2):
			length = len(str2)
		else:
			length = len(str1)
		(str1_pointer, str2_pointer) = (0, 0)
		while str2_pointer < length:
			if str1[str1_pointer] == str2[str2_pointer]:
				if str1_pointer == 0:
					ans[0] = str1_pointer
				if str1_pointer > ans[1]:
					ans[1] = str1_pointer
				str1_pointer += 1
			else:
				str1_pointer = 0
			str2_pointer += 1
		return ans


class Solution:

	def longestCommonPrefix(self, str1, str2):
		l = []
		if str1[0] not in str2:
			return [-1, -1]
		else:
			i = 0
			s1 = ''
			while i < len(str1):
				s1 += str1[i]
				if s1 in str2:
					i += 1
				else:
					break
			return [0, len(s1) - 2]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		n1 = len(str1)
		n2 = len(str2)
		m = -1
		p = 0
		i = 0
		c = 0
		while p < n2:
			if str1[i] == str2[p]:
				c += 1
				i += 1
				p += 1
			else:
				c = 0
				i = 0
				p += 1
			m = max(m, c - 1)
		if m == -1:
			return [-1, -1]
		return [0, m]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		j = 0
		m = -1
		while j < len(str2):
			f = 0
			i = 0
			while j < len(str2) and str2[j] == str1[i]:
				j += 1
				i += 1
				f = 1
			if f != 1:
				j += 1
			m = max(m, i - 1)
		if m < 0:
			return (-1, -1)
		return (0, m)


class Solution:

	def longestCommonPrefix(self, str1, str2):
		strings = [str1, str2]
		(LCP, index) = ('', [-1, -1])
		for i in range(len(str1)):
			prefix = str1[:i + 1]
			if prefix in str2:
				LCP = prefix
				index = [0, i]
		return index


class Solution:

	def longestCommonPrefix(self, str1, str2):
		m = -float('inf')
		for i in range(len(str2)):
			if str2[i] == str1[0]:
				c = 1
				while i + c < len(str2) and c < len(str1) and (str2[i + c] == str1[c]):
					c += 1
				m = max(m, c)
		if m > 0:
			return (0, m - 1)
		else:
			return (-1, -1)


class Solution:

	def longestCommonPrefix(self, str1, str2):
		s = ''
		ans = [0]
		for i in range(len(str1)):
			s = s + str1[i]
			if s not in str2:
				ans.append(i - 1)
		if ans[1] == -1:
			return [-1, -1]
		else:
			return ans


class Solution:

	def longestCommonPrefix(self, str1, str2):
		j = -1
		if len(str1) > 1000:
			return [-1]
		for i in range(len(str1)):
			if str2.find(str1[:i + 1]) == -1:
				break
			j = i
		if j == -1:
			return [-1]
		return [0, j]


class Solution:

	def longestCommonPrefix(self, str1, str2):
		if str1[0] not in str2:
			return [-1, -1]
		s = ''
		for i in range(len(str1)):
			temp = s
			s += str1[i]
			if s not in str2:
				break
		return [0, i - 1]