Вводятся некоторые слова одинаковой длины, состоящие из латинских букв (конец ввода — пустая строка). Слова можно сгруппировать попарно так, что в каждой паре не менее, чем первые k букв совпадают. Найти и вывести максимально возможное k. Количество слов чётное, не более 2·10⁵, суммарная длина всех слов — не более 2·10⁶.
babbdp bbbbfr bbbblx babbjv aaabbn bbabkw aaaags aaaaam ababco bbabeq ababiu aaabht
Подсказка: условие выполнимо, когда одинаковых начал длины k чётное количество.
4
Спойлер:
Отсортируем слова words
Будем искать максимально возможное k, при котором количество одинаковых префиксов words[i][:k] чётно (часть тестов можно пройти с таким решением)
Заметим, что для этого достаточно просматривать упорядоченные слова, но проверять не words[i][:k], а цепочки одинаковых букв words[i][k-1]: их длины должны быть чётными. В самом деле:
Допустим, все префиксы words[i][:k - 1] парные
Предположим, что среди префиксов words[i][:k] есть непарные, но все цепочки одинаковых букв в последовательности words[i][k-1] имеют чётную длину.
Это значит, что есть такие две цепочки нечётной длины words[i₀][k - 1] … words[i₁][k - 1] и words[i₁ + 1][k - 1] … words[i₂][k - 1], что
Буквы в этих цепочках совпадают (поэтому длина words[i₀][k - 1] … words[i₂][k - 1] чётна)
Префиксы words[i₀][:k] … words[i₁][:k] одинаковы, но не равны другим одинаковым префиксам words[i₁ + 1][:k] … words[i₂][:k]
Рассмотрим первую тройку i₀, i₁, i₂.
Цепочка words[i₀][k - 1] … words[i₁][k - 1] имеет нечётную длину. По предположению (3) это окончание последовательности с одинаковым чуть более коротким префиксом words[i₁][:k - 1]
Так как по предположению (1) длина последовательности words[i₁][:k - 1] чётна, в ней должна встретиться минимум ещё одна цепочка words[j₀][k - 1] … words[j₁][k - 1] нечётной длины
Получаем противоречие: согласно (5) j₁ должно быть меньше i₀, но в (4) мы рассматривали первую из цепочек нечётной длины.