Given a pattern string and a test string, If the pattern is preceded by a ^, the pattern(excluding the ^) will be matched with the starting position of the text string. Similarly, if it is preceded by a $, the pattern(excluding the ^) will be matched with the ending position of the text string. If no such markers are present, it will be checked whether pattern is a substring of test.
 
Example 1:
Input:
P = "^coal"
S = "coaltar"
Output:
1
Explanation:
The pattern "coal" is present at the
beginning of the string, so Output is 1.
Example 2:
Input:
P = "tar$"
S = "coaltar"
Output:
1
Explanation: 
The pattern "tar" is present at the
end of the string, so Output is 1.
Example 3:
Input:
P = "rat"
S = "algorate"
Output:
1
Explanation:
The pattern "rat" is present as a
substring of the string S,
so Output is 1.
Example 4:
Input:
P = "abcd"
S = "efgh"
Output:
0
Explanation:
There is no substring which is equal
to P in string S, so output is 0.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function isPatternPresent() which takes Strings P and S as input and returns 0 or 1.
 
Expected Time Complexity: O(|P|*|S|)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= |S| <= 10^{5}
1 <= |P| <= 10
String S may contain both Uppercase and Lowercase letters.

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(|P|*|S|)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def isPatternPresent(self, S , P):

        # code here 

Solutions:
import re

class Solution:

	def isPatternPresent(self, S, P):
		if len(re.findall(P, S)) > 0:
			return 1
		else:
			return 0


import re

class Solution:

	def isPatternPresent(self, S, P):
		if re.search(P, S):
			return 1
		return 0


import re

class Solution:

	def isPatternPresent(self, s, p):
		if re.findall(P, S):
			return 1
		return 0


class Solution:

	def isPatternPresent(self, S, P):
		if len(P) == 0 or (len(P) == 1 and (P[0] == '^' or P[0] == '$')):
			return 1
		if P[0] == '^':
			if P[1:] in S and S.index(P[1:]) == 0:
				return 1
			return 0
		if P[-1] == '$':
			if len(P) == 2:
				if S[-1] == P[0]:
					return 1
				return 0
			if P[:-1] in S and S.index(P[:-1]) == len(S) - len(P) + 1:
				return 1
			return 0
		if P in S:
			return 1
		return 0


class Solution:

	def isPatternPresent(self, S, P):
		ima = 0
		if '^' in P:
			ima = 1
		elif '$' in P:
			ima = 2
		if ima == 0:
			if P in S:
				return 1
			else:
				return 0
		else:
			if ima == 1:
				if P[1:] in S[0:len(P) - 1]:
					return 1
				else:
					return 0
			if ima == 2:
				if P[0:len(P) - 1] in S[len(S) - len(P[1:]):]:
					return 1
				else:
					return 0


import re

class Solution:

	def isPatternPresent(self, S, P):
		end = False
		st = False
		if P[len(P) - 1] == '$':
			end = True
			P = P[0:len(P) - 1]
		if P[0] == '^':
			st = True
			P = P[1:]
		m = re.search(P, S)
		if m is None:
			return 0
		if st:
			if m.span()[0] == 0:
				return 1
			else:
				return 0
		if end:
			if m.span()[1] == len(S):
				return 1
			else:
				for m in re.finditer(P, S):
					if m.end() == len(S):
						return 1
				return 0
		return 1


class Solution:

	def isPatternPresent(self, S, P):
		n = len(P) - 1
		return int(P[0] == '^' and P[1:] == S[:n] or (P[-1] == '$' and P[:-1] == S[-n:]) or P in S)


import re

class Solution:

	def isPatternPresent(self, S, P):
		patt = re.compile(P)
		for i in patt.finditer(S):
			return 1
		return 0


class Solution:

	def isPatternPresent(self, S, P):
		if P[0] == '^':
			return int(S.startswith(P[1:]))
		elif P[-1] == '$':
			return int(S.endswith(P[:len(P) - 1]))
		else:
			return 1 if S.find(P) >= 0 else 0


import re

class Solution:

	def isPatternPresent(self, S, P):
		if P[0] != '^' or P[len(P) - 1] != '$':
			pattern = re.compile(P)
			match = re.findall(P, S)
			if match:
				return 1
			else:
				return 0
		elif P[0] == '^':
			pattern = re.compile(P)
			match = re.findall(P, S)
			if match:
				return 1
			else:
				return 0
		elif P[len(P) - 1] == '$':
			pattern = re.compile(P)
			match = re.findall(P, S)
			if match:
				return 1
			else:
				return 0
		else:
			return 0


class Solution:

	def isPatternPresent(self, S, P):
		n = len(P)
		if P[0] == '^':
			p = P[1:n]
			if S[0:n - 1] == p:
				return 1
			return 0
		elif P[n - 1] == '$':
			n1 = len(S)
			p = P[0:n - 1]
			if S[n1 - n + 1:n1] == p:
				return 1
			return 0
		else:
			n1 = len(S)
			for i in range(n1 - n):
				if S[i:i + n] == P:
					return 1
			return 0


class Solution:

	def isPatternPresent(self, S, P):
		n = len(S)
		m = len(P)
		(beg, end) = (None, None)
		if P[0] == '^':
			beg = 0
		elif P[m - 1] == '$':
			end = n - 1
		else:
			if P in S:
				return 1
			return 0
		if beg == 0:
			for i in range(1, m):
				if S[i - 1] != P[i]:
					return 0
			return 1
		else:
			j = n - 1
			for i in range(m - 2, -1, -1):
				if S[j] == P[i]:
					j -= 1
				else:
					return 0
			return 1


class Solution:

	def isPatternPresent(self, S, P):
		if P[0] == '^':
			n = len(P)
			if P[1:] == S[:n - 1]:
				return 1
			return 0
		if P[-1] == '$':
			n = len(P)
			q = len(S)
			if P[:n - 1] == S[q - (n - 1):]:
				return 1
			return 0
		if P in S:
			return 1
		return 0


class Solution:

	def isPatternPresent(self, S, P):
		if '^' in P:
			P = P[1:]
			if P in S:
				if S.index(P) == 0:
					return 1
				return 0
		elif '$' in P:
			P = P[:-1]
			P = P[::-1]
			S = S[::-1]
			if P in S:
				if S.index(P) == 0:
					return 1
				return 0
		else:
			if P in S:
				return 1
			return 0
		return 0


class Solution:

	def isPatternPresent(self, S, P):
		n = len(S)
		m = len(P)
		s2 = ''
		for i in P:
			if not i == '^' and (not i == '$'):
				s2 = s2 + i
		val = self.LongestCommonSubstring(S, s2, n, len(s2))
		if val == len(s2):
			if P[0] == '^':
				if P[1] == S[0]:
					return 1
				else:
					return 0
			elif P[m - 1] == '$':
				if P[m - 2] == S[n - 1]:
					return 1
				else:
					return 0
			else:
				return 1
		else:
			return 0

	def LongestCommonSubstring(self, s1, s2, n, m):
		dp = [[0 for i in range(m + 1)] for j in range(n + 1)]
		maximum = 0
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if s1[i - 1] == s2[j - 1]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
					maximum = max(maximum, dp[i][j])
				else:
					dp[i][j] = 0
		return maximum
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		P = input()
		S = input()
		ob = Solution()
		print(ob.isPatternPresent(S, P))


import re

class Solution:

	def isPatternPresent(self, S, P):
		x = re.findall(P, S)
		if x:
			return 1
		else:
			return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		P = input()
		S = input()
		ob = Solution()
		print(ob.isPatternPresent(S, P))


class Solution:

	def isPatternPresent(self, s, p):
		if p[0] == '^':
			p = p[1:]
			for i in range(len(p)):
				if p[i] == s[i]:
					continue
				else:
					return 0
			return 1
		elif p[-1] == '$' or p[-1] == '^':
			p = p[:-1]
			for i in range(1, len(p) + 1):
				if p[-i] == s[-1]:
					continue
				else:
					return 0
			return 1
		elif p in s:
			return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		P = input()
		S = input()
		ob = Solution()
		print(ob.isPatternPresent(S, P))


class Solution:

	def isPatternPresent(self, S, P):
		if P[0] == '^':
			if P[1:len(P)] == S[0:len(P) - 1]:
				return 1
			else:
				return 0
		if P[len(P) - 1] == '$':
			if S[len(S) - len(P) + 1:len(S)] == P[0:len(P) - 1]:
				return 1
			else:
				return 0
		for i in range(len(S)):
			if S[i:len(P) + i] == P:
				return 1
		return 0
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		P = input()
		S = input()
		ob = Solution()
		print(ob.isPatternPresent(S, P))


class Solution:

	def isPatternPresent(self, S, P):
		if P[0] == '^':
			if P[-1] == '$':
				P = P[1:-1]
				if len(P) != len(S):
					return 0
				else:
					for i in range(len(S) - 1, -1, -1):
						if S[i] != P[i]:
							return 0
					else:
						return 1
			else:
				return int(P[1:] == S[:len(P)])
		elif P[-1] == '$':
			return int(P[:-1] == S[1 - len(P):])
		else:
			return int(P in S)


class Solution:

	def isPatternPresent(self, str, pat):
		if len(pat) > len(str):
			return False
		if pat[0] == '^':
			i = 1
			j = 0
			while i < len(pat):
				if pat[i] != str[j]:
					return 0
				i += 1
				j += 1
			return 1
		if pat[len(pat) - 1] == '$':
			i = len(pat) - 2
			j = len(str) - 1
			while i >= 0:
				if pat[i] != str[j]:
					return 0
				i -= 1
				j -= 1
			return 1
		if pat in str:
			return 1
		return 0


import re

class Solution:

	def isPatternPresent(self, S, P):
		patt = re.compile(P)
		k = patt.findall(S)
		if len(k) != 0:
			return 1
		return 0


import re

class Solution:

	def isPatternPresent(self, S, P):
		return int(bool(re.search(P, S)))


class Solution:

	def isPatternPresent(self, S, P):
		if P[-1] == '$':
			i = len(P) - 2
			j = len(S) - 1
			while j > 0 and i >= 0:
				if S[j] != P[i]:
					return 0
				i -= 1
				j -= 1
			return 1
		elif P[0] == '^':
			i = 1
			j = 0
			while j < len(S) and i < len(P):
				if S[j] != P[i]:
					return 0
				(i, j) = (i + 1, j + 1)
			return 1
		else:
			i = 0
			j = 0
			while i < len(P) and j < len(S):
				if P[i] != S[j]:
					i = 0
				elif i == len(P) - 1:
					return 1
				else:
					i += 1
				j += 1
			return 0


class Solution:

	def isPatternPresent(self, s, p):
		if p[0] == '^':
			p = p[1:]
			n = len(p)
			if p == s[:n]:
				return 1
			else:
				return 0
		elif p[-1] == '$':
			n = len(p) - 1
			p = p[:n]
			if p == s[len(s) - n:]:
				return 1
			else:
				return 0
		elif p in s:
			return 1
		else:
			return 0


class Solution:

	def isPatternPresent(self, S, P):
		i = 0
		j = 0
		ans = ''
		if P[0] == '^':
			P = P[1:]
			if S[:len(P)] == P:
				return 1
			else:
				return 0
		elif P[-1] == '$':
			P = P[:-1]
			if S[-len(P):] == P:
				return 1
			else:
				return 0
		else:
			n = len(S)
			m = len(P)
			for i in range(0, n - m):
				if S[i:i + m] == P:
					return 1
			return 0

	def isPatternPresent1(self, S, P):
		if P[0] == '^':
			P = P[1:]
		if P[-1] == '$':
			P = P[:-1]
		n = len(S)
		m = len(P)
		dp = [[0] * (m + 1) for i in range(n + 1)]
		for i in range(1, n + 1):
			for j in range(1, m + 1):
				if P[j - 1] == S[i - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		if dp[n][m] == m:
			return 1
		else:
			return 0


class Solution:

	def isPatternPresent(self, S, P):
		m = len(S)
		n = len(P)
		if P[0] == '^':
			for i in range(1, n):
				if P[i] != S[i - 1]:
					return 0
			return 1
		elif P[n - 1] == '$':
			j = m - 1
			for i in range(n - 2, -1, -1):
				if P[i] != S[j]:
					return 0
				j -= 1
			return 1
		else:
			i = 0
			j = 0
			while i < m and j < n:
				if P[j] == S[i]:
					i += 1
					j += 1
				else:
					if j != 0:
						j = 0
					i += 1
			if j == n:
				return 1
			else:
				return 0


import re

class Solution:

	def isPatternPresent(self, S, P):
		return 0 if re.search(P, S) is None else 1


class Solution:

	def isPatternPresent(self, S, P):
		if P[0] == '^':
			if P[1:] == S[:len(P) - 1]:
				return 1
		if P[-1] == '$':
			if P[-2::-1] == S[:-len(P):-1]:
				return 1
		if S.find(P) != -1:
			return 1
		return 0


class Solution:

	def isPatternPresent(self, S, P):
		cap = False
		end = False
		if P[0] == '^':
			cap = True
		if P[len(P) - 1] == '$':
			end = True
		if cap and end:
			if P[1:len(P) - 2] == S:
				return 1
			else:
				return 0
		if cap:
			if S.find(P[1:]) == 0:
				return 1
			else:
				return 0
		if end:
			if S[::-1].find(P[::-1][1:]) == 0:
				return 1
			else:
				return 0
		if S.find(P) != -1:
			return 1
		return 0


class Solution:

	def isPatternPresent(self, S, P):
		n = len(P)
		m = len(S)
		if P[0] == '^':
			if P[1:n] == S[:n - 1]:
				return 1
		elif P[-1] == '$':
			j = n - 2
			k = m - 1
			while j >= 0 and k >= 0:
				if P[j] != S[k]:
					return 0
				j -= 1
				k -= 1
			return 1
		elif P in S:
			return 1
		return 0


class Solution:

	def isPatternPresent(self, S, P):
		start = False
		end = False
		if P and P[0] == '^':
			start = True
		if P and P[-1] == '$':
			end = True
		n_p = len(P)
		n_s = len(S)
		if start and end:
			tmp_str = P[i + 1:-1] if n_p > 2 else ''
			if tmp_str == S:
				return 1
		elif start:
			tmp_str = P[1:] if n_p > 1 else ''
			if S.startswith(tmp_str):
				return 1
		elif end:
			tmp_str1 = P[:-1] if n_p > 1 else ''
			n_p = n_p - 1
			tmp_str2 = S[n_s - n_p:] if n_s - n_p > -1 else ''
			if tmp_str1 == tmp_str2:
				return 1
		elif P in S:
			return 1
		return 0


import re

class Solution:

	def isPatternPresent(self, S, P):
		a = re.findall(P, S)
		if a != []:
			return 1
		return 0


class Solution:

	def isPatternPresent(self, S, P):
		if P[0] == '^':
			S_ = P[1:]
			n = len(S)
			m = len(S_)
			all_match = True
			for i in range(m):
				if S_[i] != S[i]:
					all_match = False
					break
			if all_match:
				return 1
			else:
				return 0
		elif P[len(P) - 1] == '$':
			S_ = P[0:len(P) - 1]
			n = len(S)
			m = len(S_)
			all_match = True
			for i in range(m):
				if S_[i] != S[n - m + i]:
					all_match = False
					break
			if all_match:
				return 1
			else:
				return 0
		elif P in S:
			return 1
		else:
			return 0


class Solution:

	def isPatternPresent(self, S, P):
		n = len(S)
		m = len(P)
		output = 1
		if P[0] == '^':
			if m > n + 1:
				output = 0
			for i in range(1, m):
				if S[i - 1] != P[i]:
					output = 0
		elif P[-1] == '$':
			if m > n + 1:
				output = 0
			x = n - (m - 1)
			for i in range(m - 1):
				if S[x + i] != P[i]:
					output = 0
		else:
			output = 0
			for i in range(n - m + 1):
				check = ''
				for j in range(m):
					check += S[i + j]
				if check == P:
					output = 1
		if output == 1:
			return 1
		else:
			return 0


import math

class Solution:

	def isPatternPresent(self, S, P):
		if P[0] == '^':
			P = P[1:]
			t = [[0 for i in range(len(P) + 1)] for j in range(len(P) + 1)]
			result = -math.inf
			for i in range(1, len(P) + 1):
				for j in range(1, len(P) + 1):
					if P[i - 1] == S[j - 1]:
						t[i][j] = 1 + t[i - 1][j - 1]
						result = max(result, t[i][j])
					else:
						t[i][j] = 0
			if result == len(P):
				return 1
			else:
				return 0
		elif P[-1] == '$':
			P = P[::-1]
			P = P[1:]
			S = S[::-1]
			t = [[0 for i in range(len(P) + 1)] for j in range(len(P) + 1)]
			result = -math.inf
			for i in range(1, len(P) + 1):
				for j in range(1, len(P) + 1):
					if P[i - 1] == S[j - 1]:
						t[i][j] = 1 + t[i - 1][j - 1]
						result = max(result, t[i][j])
					else:
						t[i][j] = 0
			if result == len(P):
				return 1
			else:
				return 0
		else:
			t = [[0 for i in range(len(S) + 1)] for j in range(len(P) + 1)]
			result = -math.inf
			for i in range(1, len(P) + 1):
				for j in range(1, len(S) + 1):
					if P[i - 1] == S[j - 1]:
						t[i][j] = 1 + t[i - 1][j - 1]
						result = max(result, t[i][j])
					else:
						t[i][j] = 0
			if result == len(P) and result <= len(S):
				return 1
			else:
				return 0


import re

class Solution:

	def isPatternPresent(self, S, P):
		pattern = re.compile(P)
		if pattern.search(S):
			return 1
		elif P in S:
			return 1
		return 0


class Solution:

	def isPatternPresent(self, S, P):
		lenP = len(P)
		lenS = len(S)
		if P[0] == '^':
			if P[1:] == S[:lenP - 1]:
				return 1
			else:
				return 0
		elif P[-1] == '$':
			if P[:lenP - 1] == S[lenS - lenP + 1:]:
				return 1
			else:
				return 0
		elif P in S:
			return 1
		else:
			return 0


import re

class Solution:

	def isPatternPresent(self, S, P):
		matched = re.search('%s' % P, S)
		if matched:
			return 1
		else:
			return 0


class Solution:

	def isPatternPresent(self, S, P):
		t = ''
		if P.startswith('^'):
			t = P[1:]
			return 1 if S.startswith(t) else 0
		elif P.endswith('$'):
			t = P[:-1]
			return 1 if S.endswith(t) else 0
		else:
			t = P
			return 1 if t in S else 0


class Solution:

	def isPatternPresent(self, S, P):
		res = False
		if P[0] == '^':
			res = S.startswith(P[1:])
		elif P[-1] == '$':
			res = S.endswith(P[:-1])
		else:
			res = P in S
		return 1 if res else 0


import re

class Solution:

	def isPatternPresent(self, S, P):
		pat = re.compile(P)
		match = re.search(pat, S)
		if match:
			return 1
		else:
			return 0