Correcting Curiosity

Curiosity is the rover that explores Gale Crater on Mars. It recently found evidence of water in Martian soil, which makes planning the future manned missions easier.

Curiosity communicates with Earth directly at speeds up to 32 Kbit/s, but a signal needs 14 minutes and 6 seconds on average to travel between Earth and Mars.

Matt Heverly, the rover's driver, explains it this way. "You have just seen a stone and applied brakes, but you know that the rover is already passing that stone. So we just plan the route, then write down a list of simple textual commands: move one meter ahead, turn left, make a photo and so on."

Sometimes you have to react to an unexpected event very fast. If the cameras have seen something interesting, you may want to change the route of the rover and take one more photo. To do that you send a substitution command of the form s/⟨string⟩/⟨replacement⟩/g. It walks from the leftmost occurrence of ⟨string⟩ and replaces every occurrence with ⟨replacement⟩.

More formally, if $A$ is a non-empty string and $B$ is a string, applying the substitution command s/A/B/g to a string $S$ works like this.

1. Find the leftmost occurrence of $A$ in $S$, so that $S = S_L + A + S_R$.
2. If there is no such occurrence, stop. Then $S$ is the answer.
3. Let $R$ be the result of applying s/A/B/g to $S_R$.
4. The answer is $S_L + B + R$.

Two things follow.

1. If two occurrences of $A$ in $S$ overlap, only the leftmost one is replaced. Applying s/aba/c/g to abababa yields cbc: replacing the first aba turns the string into cbaba, and after that only the last aba can be replaced.
2. No substitution uses the result of a previous substitution. Applying s/a/ab/g to a yields ab, and applying s/a/ba/g to a yields ba.

The longer the command, the more time it takes to transmit. Find the shortest substitution command that turns the initial string into the final string.

The first line contains the initial string and the second line contains the final string. Both strings are non-empty and their lengths do not exceed 2000 characters. The strings contain only English letters, spaces and punctuation signs (commas, colons, semicolons and hyphens: , : ; -). The two given strings are different.

Print one integer, the length of the shortest substitution command that transforms the initial string into the final string.

The command s/A/B/g is $|A| + |B| + 5$ characters long. Such a command always exists.