Limits
500ms, 512 MB

Do you know what is a **sub-sequence**?

A sub-sequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.

You will be given two strings **A** and **B**. It is guaranteed that string **B** will be found one or more times as a sub-sequence in string **A**. Among all possible such sub-sequences, you have to find the one with the smallest summation of distance.

Let string **A** = “abbccfc” and string **B** = “acc”. String **B** has appeared three times as a sub- sequence in string **A**.

For the first sub-sequence, first character appeared at 0th position, the second one at 3rd position and third one at 4th position. For the first sub-sequence, summation of distance would be |3 - 0| + |4 - 3| = 4.

Respectively, for the second sub-sequence,the first character appeared at 0th position,the second one at 3rd position and the third one at 6th position. For that summation of distance would be |3 - 0| + |6 - 3| = 6.

Respectively, for the third sub-sequence, the first character appeared at 0th position, the second one at 4th position and the third one at 6th position. For that summation of distance would be |4 - 0| + |6 - 4| = 6.

To clarify more, for each two consecutive elements of string **B**, we are adding the absolute difference between the indices in string **A** where these two elements of **B** occur.

So, we can see the smallest summation of distance is 4.

The first line contains a string **A** (1≤|**A**|≤105) consisting of lowercase English letters.

The second line contains a string **B** (1≤|**B**|≤10) consisting of lowercase English letters.

Print a single integer, the smallest summation of distance.

Input | Output |
---|---|

abcefabxyb bb | 3 |

Input | Output |
---|---|

abbccfc acc | 4 |

Input | Output |
---|---|

abb a | 0 |

Login to submit.

67%
Solution Ratio

dip_BRUREarliest,

siam009Fastest, 0.0s

S_SubrataLightest, 131 kB

Shahe.335410Shortest, 793B

Toph uses cookies. By continuing you agree to our Cookie Policy.