Longest Contiguous Prefix Subsequence

We define that a string S contains string T if T is a subsequence of S, i.e., T can be obtained by deleting some (possibly zero) characters from S without changing the order of the remaining characters.

Given two strings S and T, find the maximum length L such that the first L characters of T form a subsequence of S. Formally, find the largest integer L (0 ≤ L ≤ |T|) such that
\(T[1\ldots L]\) is a subsequence of S.

Input Format: The input consists of two lines. The first line contains the string S, and the second line contains the string T.

Output Format: Output a single integer representing the maximum L that satisfies the condition.

inputFormat

The input contains two lines:

• First line: string S.
• Second line: string T.

outputFormat

Output a single integer denoting the maximum length L such that the first L characters of T form a subsequence of S.

sample

abcde
ace

3