Make Strings Great Again!

Peregrine_Falcon Replay of VU CSE Tech Fes...
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.

Input

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.

Output

Print a single integer, the smallest summation of distance.

Samples

InputOutput
abcefabxyb
bb
3
InputOutput
abbccfc
acc
4
InputOutput
abb
a
0

Submit

Login to submit.

Statistics

67% Solution Ratio
dip_BRUREarliest, Dec '19
siam009Fastest, 0.0s
S_SubrataLightest, 131 kB
Shahe.335410Shortest, 793B
Toph uses cookies. By continuing you agree to our Cookie Policy.