A Martian boy is named s — he has got this name quite recently from his parents for his coming of age birthday. Now he enjoys looking for his name everywhere. If he sees that he can obtain his name from some string by removing zero or more letters (at that, the remaining letters remain in the same order), he gets happy. For example, if s=«aba», then strings «baobab», «aabbaa», «helloabahello» make him very happy and strings «aab», «baaa» and «helloabhello» do not.

However rather than being happy once, he loves twice as much being happy twice! So, when he got string t as a present, he wanted to cut it in two parts (the left part and the right part) so that each part made him happy.

Help s determine the number of distinct ways to cut the given string t into two parts in the required manner.


-----Input-----

The first line contains string s, consisting of lowercase English letters. The length of string s is from 1 to 1000 letters.

The second line contains string t, that also consists of lowercase English letters. The length of string t is from 1 to 10^6 letters.


-----Output-----

Print the sought number of ways to cut string t in two so that each part made s happy. 


-----Examples-----
Input
aba
baobababbah

Output
2

Input
mars
sunvenusearthmarsjupitersaturnuranusneptune

Output
0

Difficulty: MEDIUM
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
name = input()
text = input()

def fun():
	first_end = len(text)
	last_start = 0
	current_index = 0
	for i in range(len(text)):
		if text[i] == name[current_index]:
			current_index += 1
			if current_index == len(name):
				first_end = i
				break
	current_index = len(name) - 1
	for i in range(len(text) - 1, first_end, -1):
		if text[i] == name[current_index]:
			current_index -= 1
			if current_index == -1:
				last_start = i
				break
	diff = last_start - first_end
	if diff < 1:
		print('0')
	else:
		print(diff)
fun()


s1 = input()
s2 = input()
len1 = len(s1)
len2 = len(s2)
l = 1
r = 0
got = 0
for i in range(0, len2):
	if s2[i] == s1[got]:
		got = got + 1
		if got == len1:
			l = i
			break
got = len1 - 1
for j in range(0, len2):
	i = len2 - j - 1
	if s2[i] == s1[got]:
		got = got - 1
		if got < 0:
			r = i - 1
			break
if l <= r:
	print(r - l + 1)
else:
	print('0')


s = input().rstrip()
line = input().rstrip()
i = 0
il = 0
while i != len(s) and il < len(line):
	if s[i] == line[il]:
		i += 1
	il += 1
x = il - 1
i = len(s) - 1
il = len(line) - 1
while i >= 0 and il >= 0:
	if s[i] == line[il]:
		i -= 1
	il -= 1
y = il + 1
if y - x > 0:
	print(y - x)
else:
	print(0)


s = input()
t = input()
reverse_s = s[::-1]
reverse_t = t[::-1]
check = 0
sequence = []
sequence1 = []
for i in range(0, len(t)):
	if t[i] == s[check]:
		sequence.append(i)
		check += 1
		if check == len(s):
			break
check = 0
for i in range(0, len(reverse_t)):
	if reverse_t[i] == reverse_s[check]:
		sequence1.append(i)
		check += 1
		if check == len(reverse_s):
			break
wynik = 0
if len(sequence) > 0 and len(sequence1) > 0:
	o = sequence.pop()
	p = len(t) - sequence1.pop() - 1
	for i in range(o, p):
		wynik += 1
print(wynik)


import random
import math
from collections import defaultdict
import itertools
from sys import stdin, stdout
import sys
import operator
from decimal import Decimal
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

def MI():
	return map(int, sys.stdin.buffer.readline().split())

def LI():
	return list(map(int, sys.stdin.buffer.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()

def li():
	return [int(i) for i in input().split()]

def lli(rows):
	return [li() for _ in range(rows)]

def si():
	return input()

def ii():
	return int(input())

def ins():
	return input().split()

def main():
	s = si()
	t = si()
	ls = len(s)
	lt = len(t)
	tin = 0
	sin = 0
	flag = 1
	while tin < lt:
		if s[sin] == t[tin]:
			sin += 1
		if sin == ls:
			flag = 0
			break
		tin += 1
	if flag == 1:
		print(0)
	else:
		tmpt = t[tin + 1:][::-1]
		tmps = s[::-1]
		lt = len(tmpt)
		ls = len(tmps)
		tin = 0
		sin = 0
		flag = 1
		while tin < lt:
			if tmps[sin] == tmpt[tin]:
				sin += 1
			if sin == ls:
				flag = 0
				break
			tin += 1
		if flag == 1:
			print(0)
		else:
			print(lt - tin)
main()


import sys
s = input()
t = input()
has = True
index_old = -1
for i in list(s):
	index = t.find(i, index_old + 1)
	has = index > index_old
	index_old = index
	if not has:
		print(0)
		sys.exit(0)
left = index_old + 1
index_old = len(t)
for i in s[::-1]:
	index = t.rfind(i, left, index_old)
	has = index != -1 and index < index_old
	index_old = index
	if not has:
		print(0)
		sys.exit(0)
print(index_old - left + 1)


s = input().strip()
l = input().strip()
judge = True
zheng_index = []
zheng_start = 0
for i in range(len(s)):
	l_temp = l[zheng_start:]
	temp = l_temp.find(s[i]) + zheng_start
	if temp == -1:
		judge = False
		break
	else:
		if not zheng_index:
			zheng_index.append(temp)
			zheng_start = temp + 1
			continue
		if zheng_index and temp > zheng_index[-1]:
			zheng_index.append(temp)
			zheng_start = temp + 1
		else:
			judge = False
			break
dao_index = []
dao_start = 0
dao_s = s[::-1]
dao_l = l[::-1]
for chr in dao_s:
	temp = dao_l[dao_start:].find(chr) + dao_start
	if temp == -1:
		judge = False
		break
	else:
		if not dao_index:
			dao_index.append(temp)
			dao_start = temp + 1
			continue
		if dao_index and temp > dao_index[-1]:
			dao_index.append(temp)
			dao_start = temp + 1
		else:
			judge = False
			break
if judge is False:
	print(0)
else:
	final_result = len(l) - dao_index[-1] - 1 - zheng_index[-1]
	if final_result <= 0:
		print(0)
	else:
		print(final_result)


s = input()
t = input()
if len(t) <= len(s):
	print(0)
elif len(s) == 1:
	p1 = t.find(s)
	p2 = t.rfind(s)
	if p2 - p1 == 0:
		print(0)
	else:
		print(p2 - p1)
else:
	p1 = 0
	for i in range(len(s)):
		while s[i] != t[p1]:
			p1 += 1
		else:
			p1 += 1
	p1 -= 1
	p2 = len(t) - 1
	for i in range(len(s) - 1, -1, -1):
		while s[i] != t[p2]:
			p2 -= 1
		else:
			p2 -= 1
	p2 += 1
	if p2 - p1 <= 0:
		print(0)
	else:
		print(p2 - p1)


s = input()
pole = input()
t = 0
count = 0
for i in range(len(pole)):
	if pole[i] == s[t]:
		t += 1
	if t == len(s):
		break
	count += 1
t -= 1
for i in range(len(pole) - 1, -1, -1):
	if pole[i] == s[t]:
		t -= 1
	if t == -1:
		count1 = i
		break
if count1 - count > 0:
	print(count1 - count)
else:
	print(0)


from functools import reduce
from operator import *
from math import *
from sys import *
from string import *
from collections import *
setrecursionlimit(10 ** 7)
dX = [-1, 1, 0, 0, -1, 1, -1, 1]
dY = [0, 0, -1, 1, 1, -1, -1, 1]
RI = lambda : list(map(int, input().split()))
RS = lambda : input().rstrip().split()

def findMatch(a, b):
	(i, j) = (0, 0)
	while i < len(a) and j < len(b):
		if a[i] == b[j]:
			j += 1
		i += 1
	return i
s = RS()[0]
t = RS()[0]
x = findMatch(t, s)
y = len(t) - findMatch(t[::-1], s[::-1])
print(max(y - x + 1, 0))


def solve():
	s = input()
	t = input()
	ls = len(s)
	if s[ls - 1] == '\n':
		ls = ls - 1
	lt = len(t)
	if t[lt - 1] == '\n':
		lt = lt - 1
	i = 0
	j = 0
	pos = -1
	while 1:
		if s[i] == t[j]:
			i = i + 1
			j = j + 1
		else:
			j = j + 1
		if i == ls:
			pos = j
		if i == ls or j == lt:
			break
	if pos == -1:
		print(0)
		return
	i = ls - 1
	j = lt - 1
	reverse = -1
	while 1:
		if s[i] == t[j]:
			i = i - 1
			j = j - 1
		else:
			j = j - 1
		if i == -1:
			reverse = j
		if i == -1 or j == -1:
			break
	reverse = reverse + 1
	pos = pos - 1
	if reverse == -1 or reverse < pos:
		print(0)
	else:
		print(reverse - pos)
solve()


name = input()
stroka = input()
lengthName = len(name)
lengthStroka = len(stroka)
indexFirst = 0
indexLast = 0
for i in range(lengthName):
	j = 0
	while j + indexFirst != lengthStroka:
		if stroka[j + indexFirst] == name[i]:
			indexFirst = j + indexFirst + 1
			break
		j += 1
i = 0
stroka = stroka[::-1]
name = name[::-1]
for i in range(lengthName):
	j = 0
	while j + indexLast != lengthStroka:
		if stroka[j + indexLast] == name[i]:
			indexLast = j + indexLast + 1
			break
		j += 1
if lengthStroka - indexLast - indexFirst + 1 < 0:
	print(0)
else:
	print(lengthStroka - indexLast - indexFirst + 1)


class word:
	(l, r) = (-1, -1)
left_word = word()
right_word = word()
subs = input()
s = input()
pos = 0
for i in range(len(s)):
	if s[i] == subs[pos]:
		if pos == 0:
			left_word.l = i
		if pos == len(subs) - 1:
			left_word.r = i
			break
		pos += 1
pos = len(subs) - 1
for i in range(len(s) - 1, -1, -1):
	if s[i] == subs[pos]:
		if pos == len(subs) - 1:
			right_word.r = i
		if pos == 0:
			right_word.l = i
			break
		pos -= 1
print(max(0, right_word.l - left_word.r))


def main():
	s = input()
	t = input()
	(i, j, m, l) = (0, len(t) - 1, 0, len(s) - 1)
	while i < j:
		if m != len(s):
			if t[i] == s[m]:
				m += 1
			if m != len(s):
				i += 1
		if l != -1:
			if t[j] == s[l]:
				l -= 1
			if l != -1:
				j -= 1
		if m == len(s) and l == -1:
			print(j - i)
			break
	else:
		print(0)
main()


def search_podstroki(t, s):
	c1 = 0
	for i in range(len(t)):
		if t[i] == s[0]:
			s = s[1:]
			if len(s) == 0:
				c1 = -1
				return i + 1
	if c1 == 0:
		return -1
s = input()
t = input()
e = 0
if len(t) <= len(s):
	print('0')
else:
	s1 = s
	h = search_podstroki(t, s1)
	s1 = s1[::-1]
	t = t[::-1]
	g = search_podstroki(t, s1)
	if g == -1 or h == -1:
		print('0')
	else:
		g = len(t) - g + 1
		if g < h:
			print('0')
		else:
			print(g - h)


def go(s, t):
	sb = None
	si = 0
	for i in range(len(t)):
		if t[i] == s[si]:
			si += 1
			if si == 1:
				sb = (i,)
			if si == len(s):
				sb += (i,)
				return sb
	return None
s = input()
t = input()
si = 0
f = go(s, t)
s = [x for x in reversed(s)]
t = [x for x in reversed(t)]
l = go(s, t)
print(len(t) - l[1] - 1 - f[1] if f and l and (len(t) - l[1] - 1 - f[1] > 0) else 0)


s = input()
t = input()
position_left = 0
seen_left = 0
while seen_left < len(s) and position_left < len(t):
	if t[position_left] == s[seen_left]:
		seen_left += 1
	position_left += 1
if seen_left < len(s):
	print(0)
	exit(0)
position_right = len(t) - 1
seen_right = 0
while seen_right < len(s) and position_right >= 0:
	if t[position_right] == s[len(s) - seen_right - 1]:
		seen_right += 1
	position_right -= 1
if position_left <= position_right:
	print(position_right - position_left + 2)
else:
	print(0)


p = input()
s = input()
answer = 0
j = 0
mini = 0
maxi = 0
lengthP = len(p)
lengthS = len(s)
for i in range(lengthS):
	if s[i] == p[j]:
		j += 1
		if j == lengthP:
			j = 0
			answer += 1
			if answer == 1:
				mini = i
if answer > 1:
	j = lengthP - 1
	for i in range(lengthS - 1, -1, -1):
		if s[i] == p[j]:
			j -= 1
			if j == -1:
				maxi = i
				break
if answer == 1 or answer == 0:
	print(0)
else:
	print(maxi - mini)


import sys
count = 0
matrix = []
for line in sys.stdin:
	if count == 0:
		pattern = line.strip()
		count += 1
	else:
		s = line.strip()
dp1 = [0 for i in range(len(s))]
dp2 = [0 for i in range(len(s))]
i = 0
j = 0
while i < len(pattern) and j < len(s):
	if pattern[i] == s[j]:
		i += 1
	j += 1
left = len(s) + 1
if i == len(pattern):
	left = j - 1
i = len(pattern) - 1
j = len(s) - 1
while i >= 0 and j >= 0:
	if pattern[i] == s[j]:
		i -= 1
	j -= 1
right = -1
if i < 0:
	right = j + 1
res = right - left if right - left > 0 else 0
print(res)


s = input()
t = input()
(e, r) = (len(s), len(t))
(q, w) = (0, 0)
while q < e and w < r:
	if s[q] == t[w]:
		q += 1
	w += 1
t = t[::-1]
s = s[::-1]
(n, m) = (0, 0)
while n < e and m < r:
	if s[n] == t[m]:
		n += 1
	m += 1
m = r - m + 1
print([0, m - w][m > w])


import sys

def solution(s, l):
	char_pos = dict()
	charset = set(s)
	for i in range(len(l)):
		c = l[i]
		if c in charset:
			if c not in char_pos:
				char_pos[c] = [i]
			else:
				char_pos[c].append(i)
	cursors = {c: 0 for c in charset}
	end = -1
	for c in s:
		if c not in char_pos:
			return 0
		while cursors[c] < len(char_pos[c]) and char_pos[c][cursors[c]] <= end:
			cursors[c] += 1
		if cursors[c] >= len(char_pos[c]):
			return 0
		end = char_pos[c][cursors[c]]
		cursors[c] += 1
	cursors = {c: len(char_pos[c]) - 1 for c in charset}
	begin = len(l)
	for c in s[::-1]:
		while cursors[c] >= 0 and char_pos[c][cursors[c]] >= begin:
			cursors[c] -= 1
		if cursors[c] < 0:
			return 0
		begin = char_pos[c][cursors[c]]
		cursors[c] -= 1
	if begin - end <= 0:
		return 0
	return begin - end
s = sys.stdin.readline().strip()
l = sys.stdin.readline().strip()
print(solution(s, l))


__author__ = 'Руслан'
name = input()
finder = input()
left_pos = 0
right_pos = len(finder)
isfind = True
for i in name:
	left_pos = finder.find(i, left_pos)
	if left_pos == -1:
		isfind = False
		break
	else:
		left_pos += 1
if isfind:
	for i in name[::-1]:
		right_pos = finder.rfind(i, 0, right_pos)
if right_pos >= left_pos and isfind:
	print(right_pos - left_pos + 1)
else:
	print(0)


name = input()
phrase = input()
pos = []
j = 0
len_name = len(name)
len_phrase = len(phrase)
test = False
if len_name >= len_phrase:
	print(0)
	exit(0)
for (n, i) in enumerate(phrase):
	if name[j] == i:
		if not test:
			pos.append([n])
			test = True
		j += 1
		if j == len_name:
			pos[-1].append(n)
			test = False
			break
j = 0
for (n, i) in enumerate(phrase[::-1]):
	if name[len_name - 1 - j] == i:
		if not test:
			pos.append([len_phrase - n - 1])
			test = True
		j += 1
		if j == len_name:
			pos[-1].append(len_phrase - n - 1)
			test = False
			break
if pos[0][1] < pos[1][1]:
	print(pos[1][1] - pos[0][1])
else:
	print(0)


import sys
t = sys.stdin.readline().strip()
s = sys.stdin.readline().strip()
t_pos = 0
first = None
for (i, c) in enumerate(s):
	if c == t[t_pos]:
		t_pos += 1
		if t_pos == len(t):
			first = i
			break
t_pos = len(t) - 1
last = None
for (i, c) in reversed(list(enumerate(s))):
	if c == t[t_pos]:
		t_pos -= 1
		if t_pos == -1:
			last = i
			break
if first == None or last == None or first > last:
	sys.stdout.write('0\n')
else:
	sys.stdout.write(str(last - first) + '\n')


from collections import Counter
import string
import math
import sys
from fractions import Fraction

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))

def printDivisors(n):
	divisors = []
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				divisors.append(i)
			else:
				divisors.extend((i, n // i))
		i = i + 1
	return divisors

def countTotalBits(num):
	binary = bin(num)[2:]
	return len(binary)

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
s = input()
t = input()
m = len(s)
n = len(t)
j = 0
flag = 0
for i in range(n):
	if j >= m:
		break
	if t[i] == s[j]:
		j += 1
		continue
if j != m:
	print(0)
else:
	p = m - 1
	flag = 0
	for k in range(n - 1, i, -1):
		if t[k] == s[p]:
			if p == 0:
				flag = 1
				break
			p -= 1
	if flag != 1:
		print(0)
	else:
		print(k - (i - 1))


s = input()
a = input()
j = 0
v = 0
c = 0
flag = 0
if len(s) > len(a):
	pass
else:
	for i in range(len(s)):
		k = s[i]
		while j < len(a):
			if a[j] == k:
				flag += 1
				if flag == len(s):
					c = j
					break
				else:
					break
			j += 1
		j += 1
	j = len(a) - 1
	flag = 0
	for i in range(len(s) - 1, -1, -1):
		k = s[i]
		while j > c:
			if a[j] == k:
				flag += 1
				if flag == len(s):
					v = j - c
					break
				else:
					break
			j -= 1
		j -= 1
print(v)


t = input()
s = input()
l_t = len(t)
l_s = len(s)
x = 0
f = l_s + 1
for i in range(l_s):
	if t[x] == s[i]:
		x += 1
	if x == l_t:
		f = i
		break
c = -1
y = l_t - 1
for i in range(l_s - 1, -1, -1):
	if t[y] == s[i]:
		y -= 1
	if y == -1:
		c = i
		break
if c - f <= 0:
	print(0)
else:
	print(c - f)


name = input()
line = input()
i_name = 0
i_line = 0
while i_name < len(name) and i_line < len(line):
	if name[i_name] == line[i_line]:
		i_name += 1
	i_line += 1
j_name = len(name) - 1
j_line = len(line) - 1
while j_name >= 0 and j_line >= 0:
	if name[j_name] == line[j_line]:
		j_name -= 1
	j_line -= 1
if i_line <= j_line:
	print(j_line - i_line + 2)
elif i_line - 1 == j_line:
	print(1)
else:
	print(0)


import sys
s = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()
i = 0
j = 0
l = 0
r = 0
while i < len(s) and j < len(t):
	if s[i] == t[j]:
		i += 1
		j += 1
	else:
		j += 1
if i + 1 >= len(s):
	l = j
s = s[::-1]
t = t[::-1]
i = 0
j = 0
while i < len(s) and j < len(t):
	if s[i] == t[j]:
		i += 1
		j += 1
	else:
		j += 1
if i + 1 >= len(s):
	r = j
if l == 0:
	print(0)
	exit(0)
if len(t) - l - r + 1 > 0:
	print(len(t) - l - r + 1)
else:
	print(0)


__author__ = 'ruckus'
s = input()
t = input()
inlines = []
j = 0
for i in range(len(t)):
	if t[i] == s[j]:
		if j == 0:
			inlines.append([i])
		j += 1
		if j >= len(s):
			inlines[len(inlines) - 1].append(i)
			break
j = len(s) - 1
for i in range(len(t) - 1, -1, -1):
	if t[i] == s[j]:
		if j == len(s) - 1:
			inlines.append([i])
		j -= 1
		if j < 0:
			inlines[1].append(i)
			break
if len(inlines) < 2 or len(inlines[1]) < 2 or inlines[1][1] - inlines[0][1] < 0:
	print(0)
else:
	print(inlines[1][1] - inlines[0][1])


s = input()
t = input()
m = len(s)
n = len(t)
first = 0
last = n
j = 0
flag = 0
i = 0
while i < n and j < m:
	if t[i] == s[j]:
		j += 1
	i += 1
first = i - 1
if j == m:
	flag = 1
i = n - 1
j = m - 1
while i >= 0 and j >= 0:
	if t[i] == s[j]:
		j -= 1
	i -= 1
last = i + 1
if flag == 0 or last <= first:
	ans = 0
else:
	ans = last - first
print(ans)


name = input()
s = input()
name_len = len(name)
l = -1
r = len(s)
index = 0
for ch in s:
	l += 1
	if ch == name[index]:
		index += 1
	if index == name_len:
		break
index = name_len - 1
for ch in s[::-1]:
	r -= 1
	if ch == name[index]:
		index -= 1
	if index == -1:
		break
if l < r:
	print(r - l)
else:
	print(0)