Construct the String
Contest: Educational Codeforces Round 89 (Rated for Div. 2)
Difficulty rating: 2700
Tags: data structures, dp, strings

Let's denote the function $$$f(s)$$$ that takes a string $$$s$$$ consisting of lowercase Latin letters and dots, and returns a string consisting of lowercase Latin letters as follows:

1. let $$$r$$$ be an empty string;
2. process the characters of $$$s$$$ from left to right. For each character $$$c$$$, do the following: if $$$c$$$ is a lowercase Latin letter, append $$$c$$$ at the end of the string $$$r$$$; otherwise, delete the last character from $$$r$$$ (if $$$r$$$ is empty before deleting the last character — the function crashes);
3. return $$$r$$$ as the result of the function.

You are given two strings $$$s$$$ and $$$t$$$. You have to delete the minimum possible number of characters from $$$s$$$ so that $$$f(s) = t$$$ (and the function does not crash). Note that you aren't allowed to insert new characters into $$$s$$$ or reorder the existing ones.

Input format:
The input consists of two lines: the first one contains $$$s$$$ — a string consisting of lowercase Latin letters and dots, the second one contains $$$t$$$ — a string consisting of lowercase Latin letters ($$$1 \le |t| \le |s| \le 10000$$$).

Additional constraint on the input: it is possible to remove some number of characters from $$$s$$$ so that $$$f(s) = t$$$.

Output format:
Print one integer — the minimum possible number of characters you have to delete from $$$s$$$ so $$$f(s)$$$ does not crash and returns $$$t$$$ as the result of the function.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Example input:
a.ba.b.
abb

Example output:
2

Example input:
.bbac..a.c.cd
bacd

Example output:
3

Editorial:
The core idea of the solution is the following dynamic programming: $$$dp_{i, j}$$$ is the minimum number of characters we have to delete if we considered a subsequence of $$$i$$$ first characters of $$$s$$$, and it maps to $$$j$$$ first characters of $$$t$$$.
There are three obvious transitions in this dynamic programming:
• we can go from $$$dp_{i, j}$$$ to $$$dp_{i + 1, j}$$$ by skipping $$$s_i$$$;
• if $$$s_i = t_j$$$, we can go from $$$dp_{i, j}$$$ to $$$dp_{i + 1, j + 1}$$$;
• if $$$s_i$$$ is a dot, we can go from $$$dp_{i, j}$$$ to $$$dp_{i + 1, j - 1}$$$.
Unfortunately, these transitions cannot fully handle the case when we want to put some character and then delete it (these transitions don't allow us to do it for any character, only for some specific ones in specific situations). To handle it, suppose we want to take the character $$$s_i$$$ and then delete it, and we model it as follows: there exists the fourth transition from $$$dp_{i,j}$$$ to $$$dp_{i+len_i, j}$$$ without deleting anything, where $$$len_i$$$ is the length of the shortest substring of $$$s$$$ starting from $$$i$$$ that becomes empty if we apply the function $$$f$$$ to it. This substring can be described as a regular bracket sequence, where opening brackets correspond to letters, and closing brackets — to dots. We can precalculate this substring for each $$$i$$$ in $$$O(n)$$$.
Why is this transition enough? Suppose we don't want to take some letter from this shortest substring in the optimal answer; since it is the shortest substring meeting these constraints, the number of letters on each prefix of it (excluding the substring itself) is greater than the number of dots, so we can instead skip the first letter and try applying this transition from $$$dp_{i + 1, j}$$$, so this case is handled. And skipping any dots from this shortest substring is also suboptimal since we have to get rid of the character $$$s_i$$$.