Для программистов в наших рядах

Интересная алгоритмическая проблемка.

Есть набор строк (одной длины, но это вроде бы неважно). Есть два параметера: Х - максимальное число позволенных do-not-care симоволов, и N - максимальное число строк в результате. Нужно разбить исходный набор в соответствии с этими параметерами, ну или установить, что это невозможно.

Например:
1 2 3 1 2 3 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 3 3 3 7 8 9

При Х = 3 результат такой: 1 2 3 ? ? ? 7 8 9, но при Х = 2 это уже не годится, нужно выдать:
1 2 3 ? ? 3 7 8 9
1 2 3 4 5 6 7 8 9

Строки запихнуты в ternary tree, которое позволяет поиск всех строк на опредленном расстоянии от данной строки, а так же поиск всех строк, удовлетворяющих шаблонам с do-not-care.

Но можно запихнуть и в какую-нибудь другую структуру.

Для программистов в наших рядах

Интересная алгоритмическая проблемка.

Есть набор строк (одной длины, но это вроде бы неважно). Есть два параметера: Х - максимальное число позволенных do-not-care симоволов, и N - максимальное число строк в результате. Нужно разбить исходный набор в соответствии с этими параметерами, ну или установить, что это невозможно.

Например:
1 2 3 1 2 3 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 3 3 3 7 8 9

При Х = 3 результат такой: 1 2 3 ? ? ? 7 8 9, но при Х = 2 это уже не годится, нужно выдать:
1 2 3 ? ? 3 7 8 9
1 2 3 4 5 6 7 8 9

Строки запихнуты в ternary tree, которое позволяет поиск всех строк на опредленном расстоянии от данной строки, а так же поиск всех строк, удовлетворяющих шаблонам с do-not-care.

Но можно запихнуть и в какую-нибудь другую структуру.