Две строки логов нужно сравнить: какой самый длинный фрагмент встречается в обеих подряд (самая длинная общая подстрока)? Функция common_fragment_length(a, b) решает это таблицей, но перепутала подстроку с подпоследовательностью. В ней две ошибки — найдите и исправьте их.
common_fragment_length("error: disk full", "warning: disk quota") # 7: ": disk " (с пробелами)
common_fragment_length("abcx", "xabc") # 3: "abc"Заготовка задачи обновилась с тех пор, как вы сохранили свой код.
Сбросить редактор к заготовке? Ваш код будет удалён.
def common_fragment_length(a: str, b: str) -> int:
"""Длина самой длинной общей подстроки a и b."""
table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
best = 0
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
table[i][j] = table[i - 1][j - 1] + 1
best = max(best, table[i][j])
else:
table[i][j] = max(table[i - 1][j], table[i][j - 1])
return table[len(a)][len(b)]Вывод обрезан: показаны первые строки.
def test_example_logs():
"""Логи: общий фрагмент «: disk » длины 7"""
got = common_fragment_length("error: disk full", "warning: disk quota")
assert got == 7, f"ожидалось 7, получено {got!r}"
def test_rotation():
"""abcx и xabc → 3"""
got = common_fragment_length("abcx", "xabc")
assert got == 3, f"ожидалось 3, получено {got!r}"
def test_scattered_is_not_substring():
"""Общие буквы вразброс — это не подстрока: axbxc и abc → 1"""
got = common_fragment_length("axbxc", "abc")
assert got == 1, f"ожидалось 1, получено {got!r}"
def test_empty():
"""Пустая строка → 0"""
assert common_fragment_length("", "abc") == 0, "пустая a"
assert common_fragment_length("abc", "") == 0, "пустая b"
def test_nothing_common():
"""Нет общих символов → 0"""
got = common_fragment_length("abc", "xyz")
assert got == 0, f"ожидалось 0, получено {got!r}"
def test_identical():
"""Одинаковые строки → длина строки"""
got = common_fragment_length("timeout", "timeout")
assert got == 7, f"ожидалось 7, получено {got!r}"
def test_more_pairs():
"""Ещё четыре пары строк — заранее посчитанные ответы"""
pairs = [("mississippi", "missouri", 4), ("banana", "ananas", 5), ("abcdef", "zcdemf", 3), ("aaaa", "aa", 2)]
for a, b, expected in pairs:
got = common_fragment_length(a, b)
assert got == expected, f"{a!r} и {b!r}: ожидалось {expected}, получено {got!r}"Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 log_common_fragment.py — тесты те же, результат покажет ✓ / ✗ и итог.
Подстрока, в отличие от подпоследовательности, должна идти подряд. Что должно оказаться в ячейке, если символы не совпали?
В задаче о подстроке ответ — не обязательно последняя ячейка таблицы. Где он может быть?
def common_fragment_length(a: str, b: str) -> int:
"""Длина самой длинной общей подстроки a и b."""
table = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
best = 0
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
table[i][j] = table[i - 1][j - 1] + 1
best = max(best, table[i][j])
else:
table[i][j] = 0
return best