Sereja and two strings
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Sereja has two strings s and w. Sereja can do 3 types of operations:
- Remove any character from the first string, this operation takes a minutes of time
- Add any character in any position of the first string, this operation takes a minutes of time
- Replace some character form first string by some other character, this operation takes b minutes of time
Sereja has k minutes to do some operations. Find the minimum time that Sereja needs to transform the first string to the second.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line contains string s. The second line contains string w. Both strings contain only lowercase Latin letters. The third line contains integers a,b and k, separated by spaces.
For each test case on different lines print the answer to the problem - minimum time required to transform the first string to the second by the operations of the first, second and third types. If you can not transform the first string to the second for the specified time, print -1.
- 1 ≤ T ≤ 10
- 1 ≤ |s|, |w| ≤ 100000
- 0 ≤ a, b, k ≤ 100
Input: 4 aaa bbbb 0 0 100 abab acac 1 1 100 baaaaa aaaaab 1 100 100 aaaaaa bbbbbb 100 100 0 Output: 0 2 2 -1
|Tags||edit-distance, medium, oct14, sereja|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.