관련된 언어

시간 제한10초메모리 제한512 MB

요약

두 문자열 A와 B, 정수 k가 주어질 때, 같은 길이를 가지면서 서로 다른 위치가 k개 이하인 부분 문자열 쌍의 최대 길이를 구한다.

난이도: 어려움10점 중 8점
유형: 이분 탐색, 동적 계획법, 문자열, 투 포인터
정답자: 아직 제출이 없습니다

문제

두 고대 언어를 연구하면서 두 언어가 가까운 친척 관계라고 증명하려 한다. 두 언어에서 "push-relabel flow algorithm"에 해당하는 단어가 하나의 조상 단어에서 유래했다고 의심하고 있다. 그렇다면 두 단어에는 서로 크게 다르지 않은 부분 문자열, 즉 비슷한 핵심이 들어 있을 것이다.

두 단어 $A$ 와 $B$ 가 주어질 때, 다음 조건을 만족하는 최대 $s$ 를 구하라. $A$ 의 연속 부분 문자열 $A'$ 과 $B$ 의 연속 부분 문자열 $B'$ 이 길이 $s$ 이고, 서로 최대 $k$ 개의 위치에서만 다르다.

입력

첫째 줄에 테스트 케이스의 수 $z$ 가 주어진다 ( $1 \leq z \leq 2000$ ). 이어서 각 테스트 케이스의 설명이 주어진다.

각 테스트 케이스는 세 줄로 이루어진다. 첫째 줄에 세 수 $n, m, k$ 가 주어진다 ( $1 \le n, m \le 4000$ ; $0 \le k \le \min(m,n)$ ). 다음 두 줄에 길이 $n$ 과 $m$ 인 두 문자열 $A$ 와 $B$ 가 주어지며, 각 문자열은 소문자 영어 알파벳으로만 이루어진다.

입력에 주어지는 모든 단어의 길이 합은 $200\,000$ 을 넘지 않는다.

출력

각 테스트 케이스마다 최대 $k$ 개의 위치에서만 다른 부분 문자열의 최대 길이를 한 줄에 출력한다.

예제1

예제 1
입력
```
1
12 13 2
hakunamatata
hienakulameta
```
예상 출력
```
9
```