题号：NC15539
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld
题目描述
As a acmer, Slp is always thinking of problems, and a new problem come to his mind. Given two stings A and B, one can delete some characters of A to get a new string A′ to make A′ and B become a great match.
A great match of A′ and B is defined as follow:
1. A′ has length of k, B has length of m (k ≤ m).
2. Define a substring of B( B1 ,B2, ... ,Bk), as a new string B′ with the same length as A′. For example, if A′has length of 3 and B is ”abcde”, the B′ will be ”abc”.
3. There are exactly p(p is a given number) i that satisfy A′i
B′i.
If A′ and B meet all the above conditions, we call A′ and B is a great match.
Given two string A, B and a number p, your should help Slp to find the minimum number of deleting characters to get a string A' that has a great match with B.
A great match of A′ and B is defined as follow:
1. A′ has length of k, B has length of m (k ≤ m).
2. Define a substring of B( B1 ,B2, ... ,Bk), as a new string B′ with the same length as A′. For example, if A′has length of 3 and B is ”abcde”, the B′ will be ”abc”.
3. There are exactly p(p is a given number) i that satisfy A′i
If A′ and B meet all the above conditions, we call A′ and B is a great match.
Given two string A, B and a number p, your should help Slp to find the minimum number of deleting characters to get a string A' that has a great match with B.
For example, if A is ”aabbcc”, B is ”abcbc” and p is 1, Slp can delete the 2nd, the 4th characters to get ”abcc” as A′. Then B′ is ”abcb”.So A′ and B′ has exactly 1 different location. So the answer is 2.
Note that Slp may delete all characters of A.
输入描述:
The first line contains an integer number T, the number of test cases.
For each test case :
The first line contains three integers n,m(0 ≤ n ≤ m ≤ 103), p(0 ≤ p ≤ 103), length of A,B and the number p.
The second line contains a string A with the length of n.
The third line contains a string B with the length of m.
It is guaranteed that the strings contains only lowercase letters.
输出描述:
For each test case print the minimum number of deleting characters to get a string A' that has a great match with B. If there is no such way print -1.