Учитывая две строки длины n, P = p1 ... pn и Q = q1 ... qn, мы определяем M (i, j, k) как число несовпадений между pi ... pi + k- 1 и qj..qj + k-1. То есть в обозначении набора, M (i, j, k) относится к размеру набора { 0<=x<k | pi+x not equal to qj+x| }.
Учитывая целое число K, ваша задача состоит в том, чтобы найти максимальную длину L такую, чтобы существовала пара индексов (i, j), для которых у нас есть M(i, j, L) <= K. Конечно, у нас также должны быть i+L-1 <=n и j+L-1 <=n.
Ввод
Первая строка ввода содержит одно целое число T (1 <= T <= 10). Т-тесты следуют.
Каждый тестовый пример состоит из целого числа K и двух строк P и Q, разделенных одним пробелом.
Выход </p>
Для каждого тестового примера выведите одно целое число L, которое является максимальным значением, для которого существует пара индексов (i, j), такая, что M (i, j, L) <= K. </p>
Ограничения
0 <= K <= длина строки P
Оба P & Q будут иметь одинаковую длину
Размер каждой строки будет максимальным 1500
Все символы в P & Q являются строчными латинскими буквами. </p>
Пример ввода
3
2 tabriz torino
0 abacba abcaba
3 helloworld yellomarin
Пример вывода
4
3
8
Пояснение:
Первый тестовый случай: если мы берем «briz» из первой строки и «orin» из второй строки, то количество несовпадений между этими двумя подстроками равно 2, а длина этих подстрок равна 4. Это мы выбрали i = 3, j = 2, L = 4, и мы имеем M (3,2,4) = 2.
Второй тестовый случай: поскольку K = 0, мы должны найти самую длинную общую подстроку для заданных входных строк. В результате мы можем выбрать «aba», и у нас нет более длинной общей подстроки между двумя строками. Итак, ответ 3 для этого теста. То есть мы выбрали i = 1, j = 4 и L = 3, и мы имеем M (1,4,3) = 0.
Третий контрольный пример: мы можем выбрать «hellowor» из первой строки и «yellomar» из второй строки. Итак, мы выбрали i = 1, j = 1 и L = 8, и мы имеем M (1,1,8) = 3. Конечно, мы также можем выбрать i = 2, j = 2 и L = 8, и мы все еще имеем M (2,2,8) = 3.
вот моя реализация
import java.io.*;
import java.util.*;
class Solution {
public static int mismatch(String a, String b, int ii, int jj, int xx) {
int i, j = 0;
for (i = 0; i < xx; i++) {
if (a.charAt(ii) != b.charAt(jj)) {
j++;
}
ii++;
jj++;
}
return j;
}
public static boolean find(int x, String a, String b, int kx) {
int nn = a.length();
for (int i = 0; i <= (nn - x); i++) {
for (int j = 0; j <= (nn - x); j++) {
int k;
k = mismatch(a, b, i, j, x);
if (k == kx) {
return true;
}
}
}
return false;
}
public static void main(String args[]) throws IOException {
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while (t > 0) {
int k, n;
String a, b;
k = scanner.nextInt();
a = scanner.next();
b = scanner.next();
n = a.length();
int i = (n + k) / 2;
int st = k, en = n
while (i != k || i != n) {
boolean ch = false, chh = false;
ch = find(i, a, b, k);
if (i != n) {
chh = find(i + 1, a, b, k);
}
if (i == n && ch == true) {
System.out.println(i);
break;
}
if (ch == true && chh == false) {
System.out.println(i);
break;
}
if (ch) {
st = i;
i = (i + en + 1) / 2;
} else {
en = i;
i = (st + i) / 2;
}
}
t--;
}
}
}
вышеприведенная реализация требует 5,1 секунды для ввода 0f длины строки 1500. Но максимальный лимит времени в java составляет 5 с. Если любой может улучшить этот код, пожалуйста, поделитесь своими соображениями