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 |