Minimum Insertions to Achieve Subsequence

You are given two strings s and t. Your task is to determine the minimum number of characters that need to be inserted into s so that t becomes a subsequence of s.

A string t is a subsequence of s if all the characters of t can be found in s in the same order (not necessarily contiguous). mathematically, if we traverse s using a pointer and match characters with t, if after the process we have matched j characters and j = |t|, then t is already a subsequence of s. Otherwise, one needs to insert the missing |t| - j characters.

In summary, if we let $$j$$ be the number of characters from t that are matched in order in s, then the answer is given by the formula:

Your solution should read input from standard input (stdin) and output the result to standard output (stdout).

inputFormat

The input consists of two lines. The first line contains the string s, and the second line contains the string t.

outputFormat

Output a single integer — the minimum number of insertions required so that t becomes a subsequence of s.

abc
ab

0