Обратное условие Фано

Иногда в условии стоит слово, мимо которого легко проскочить: обратное условие Фано. Или его называют постфиксным кодом.

Правило меняется ровно на одно слово: никакое кодовое слово не является не началом, а окончанием другого. Всё остальное — как было.

Приём: переверни и решай как обычно

Отдельную теорию учить не нужно. Переверни каждый код задом наперёд — и обратное условие превратится в обычное.

Возьмём коды: 1, 10, 100 и перевернём их: 1, 01, 001. Проверять начала мы уже умеем, а больше ничего и не требуется.

Дерево тоже работает — просто читай пути снизу вверх. Правило одно, вид другой.

Проверим на деле. Коды 1, 010, 000 обратному условию удовлетворяют: ни один из них не является окончанием другого. А кратчайшее слово, которое можно добавить четвёртой букве, — 100. Убедись сам: на 100 не заканчивается ни один из трёх.