| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 10 초 | 512 MB | 20 | 10 | 8 | 80.000% |
You are studying two ancient languages, aiming to prove that they are closely related. You suspect that the words for "push-relabel flow algorithm" in both languages stem from a single ancestor. If so, they contain similar cores, i.e. subwords that do not differ much from each other.
Given two words $A$ and $B,ドル determine the maximum possible $s,ドル for which there are connected subwords $A'$ in $A$ and $B'$ in $B$ such that $A'$ and $B'$ have length $s,ドル and differ on at most $k$ positions.
The first line of input contains the number of test cases $z$ (1ドル \leq z \leq 2000$). The descriptions of the test cases follow.
Every test case consists of three lines. The first line contains three numbers $n, m, k$ (1ドル \le n, m \le 4000$; 0ドル \le k \le \min(m,n)$). In the next two lines there are two strings $A$ and $B,ドル of lengths $n$ and $m,ドル respectively, each consisting of lowercase English letters.
The total length of all the words in the input does not exceed 200ドル,000円$.
For each test case output a single integer -- the maximum possible length of subwords that differ on at most $k$ positions.
1 12 13 2 hakunamatata hienakulameta
9