X From Y
Problem Description
Malaika is very fond of strings so whenever she gets some free time, she will keep herself engaged in string based activities.
One day, she came across a question where she will be given two strings X & Y and asked to form X from Y. The rules for forming the string are given below.
The string X should be formed with the concatenation of the sub strings of Y. You can also select the sub strings from Y in reversed order.
The length of the sub strings selected from Y should be greater than or equal to one.
Aim is to minimize the number of sub strings that are selected from Y and concatenated to form X.
A term String Factor is defined which is calculated as (number of sub strings selected from Y) * S + (number of sub strings selected from reversed Y) * R, where S and R given in the input.
You also have to minimize the String Factor while maintaining the minimum number of sub strings.
Given two strings X and Y and two integers S and R, find the minimum String Factor of the string X following above rules.
Constraints
1 <= lengths of X,Y <= 10^4
0 <= S, R <= 10^3
X, Y consists of lower case alphabets only.
Input
First line consists of string X.
Second line consists of string Y.
Third line consists of two integers S and R separated by space.
Output
Form the string X from string Y following the above rules and print the String Factor of X. Print "Impossible" if X can't be formed from Y.
Time Limit (secs)
1
Examples
Example 1
Input
niveditha
lavekdahnita
3 5
Output
17
Explanation
For forming the string niveditha from lavekdahnita, select sub strings ni from Y, ve from Y, d from Y, it from Y, ha from reversed Y. No other selections can give less than five sub strings.
String Factor = (number of sub strings selected from Y) * S + (number of sub strings selected from reversed Y) * R = (4*3) + (1*5) = 17
Example 2
Input
abcdef
pafedexycbc
4 2
Output
6
Explanation
For forming the string abcdef from pafedexycbc, select the sub string 'a' from reversed Y, bc from reversed Y, def from reversed Y. No other selections can give less than three sub strings.
String Factor = (number of sub strings selected from Y) * S + (number of sub strings selected from reversed Y) * R = (0*4) + (3*2) = 6
视频信息
答案文本
视频字幕
The X From Y problem asks us to form string X by concatenating substrings from string Y. We can use substrings from Y in normal order or reversed order. Our goal is to minimize the number of substrings first, then minimize the String Factor, which is calculated as the number of normal substrings times S plus the number of reversed substrings times R.
The problem has three main rules: we concatenate substrings from Y, we can use either normal Y or reversed Y, and each substring must have length at least one. The String Factor is calculated as the number of normal substrings times S plus the number of reversed substrings times R. We optimize in two steps: first minimize the total number of substrings, then among solutions with minimum substrings, choose the one with minimum String Factor.
Let's work through the first example. We need to form 'niveditha' from 'lavekdahnita' with S equals 3 and R equals 5. The optimal solution uses 5 substrings: 'ni', 've', 'd', and 'it' from the normal string Y, and 'ha' from the reversed string. This gives us a String Factor of 4 times 3 plus 1 times 5, which equals 17. This is optimal because no other selection can form the target string with fewer than 5 substrings.
In the second example, we form 'abcdef' from 'pafedexycbc' with S equals 4 and R equals 2. Since R is less than S, it's cheaper to use substrings from the reversed string. The optimal solution uses only reversed substrings: 'a', 'bc', and 'def' from the reversed Y. This gives us a String Factor of 0 times 4 plus 3 times 2, which equals 6. The lower cost of reversed substrings makes this strategy optimal.
We solve this problem using dynamic programming. We define dp[i] as the minimum String Factor needed to form the first i characters of X. For each position i, we try all possible substrings ending at position i, checking if they exist in either the normal Y or reversed Y. The recurrence relation is dp[i] equals the minimum of dp[j] plus the cost for all valid positions j less than i. This approach has time complexity O of X squared times Y, which is efficient for the given constraints.