prefpref

You are given two string S and T. Find the maximal length of some prefix of the string S which occurs in strings T as subsequence.

Input
The first line contains string S.
The second line contains string T.
Both strings consist of lowecase Latin letters.

Output
Output one integer - answer to the question.

Constraints
1 ≤ length of S, T ≤ 10^6

SAMPLE INPUT
digger
biggerdiagram

SAMPLE OUTPUT
3

Source: hackerearth | Difficulty: EASY
Tags: String algorithms

Ad-hoc


Solutions:

from collections import deque, defaultdict, Counter
from math import factorial
from fractions import gcd
from sys import stdin, exit
from itertools import *
import heapq
import string
import re


def prase(T):
	if T == 1:
		return list(map(int, testcase.next().strip().split()))
	return testcase.next().strip().split()

def get():
	return testcase.next().strip()
	
testcase = stdin

# code starts here
s = get()
t = get()
count = 0
n = 0
for i in s:
	for j in range(n, len(t)):
		if t[j] == i:
			count += 1
			n = j+1
			break
	else:
		break
print(count)




from collections import deque, defaultdict, Counter
from math import factorial
from fractions import gcd
from sys import stdin, exit
from itertools import *
import heapq
import string
import re


def prase(T):
	if T == 1:
		return list(map(int, testcase.next().strip().split()))
	return testcase.next().strip().split()

def get():
	return testcase.next().strip()
	
testcase = stdin

# code starts here
s = get()
t = get()
count = 0
n = 0
for i in s:
	for j in range(n, len(t)):
		if t[j] == i:
			count += 1
			n = j+1
			break
	else:
		print(count)
		exit(0)
print(count)



s = input()
t = input()

count = 0
sPos = 0
for c in t:
	if c == s[sPos]:
		count += 1
		sPos += 1
		if sPos >= len(s):
			break
print(count)
	
	



from collections import deque, defaultdict, Counter
from math import factorial
from fractions import gcd
from sys import stdin, exit
from itertools import *
import heapq
import string
import re


def prase(T):
	if T == 1:
		return list(map(int, testcase.next().strip().split()))
	return testcase.next().strip().split()

def get():
	return testcase.next().strip()
	
testcase = stdin

# code starts here
s = get()
t = get()
count = 0
n = 0
for i in s:
	for j in range(n, len(t)):
		if t[j] == i:
			count += 1
			n = j+1
			break
	else:
		break
print(count)



s = input()
t = input()

sindex = 0
tindex = 0

sLen = len(s)
tLen = len(t)

while(sindex < sLen and tindex < tLen):
	if(s[sindex] == t[tindex]):
		sindex += 1
	tindex += 1
print(sindex)



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

S = input()
T = input()

pos_s = 0

for l in T:
	if l == S[pos_s]:
		pos_s += 1
	if pos_s==len(S):
		break

print(pos_s)


s=list(input())
t=list(input())

l=len(s)
n=len(t)
i=0
j=0
arr=[]
while i<n:
	if t[i]==s[j]:
		arr.append(t[i])
		if j==l-1:
			break
		
		if j<l:
			j+=1
	i+=1
	
print(len(arr))


s=input()
t=input()
c=0
r=0
for i in range(len(t)):
	if c<len(s) and s[c]==t[i]:
		c+=1
print(c)