Здравствуйте, kov_serg, Вы писали:

_>Здравствуйте, R.K., Вы писали:

V>>>- Придумать структуру в которой можно быстро искать все строки с заданным расстоянием Хемминга в наборе битовых строк такой же длины.

RK>>Задачка для PATRICIA trie.
_>И чем суффиксное дерево поможет в поиске максимального расстояния?

Trie это не суффиксное дерево. Оно может исполнять функцию suffix tree, когда используется для индексации всех суффиксов некоторой строки. А в более простом классическом варианте trie индексирует набор строк, примерно как search tree, но с дополнительными функциями за счет того, что для ветвления в trie используются несовпадающие символы строк. В PATRICIA trie, в свою очередь, для ветвления используются несовпадающие биты строк, что позволяет автоматически решить проблему большого количества символов в алфавите и делает структуру дерева наиболее простой и эффективной из возможных — binary tree.
После того, как мы построили trie над множеством строк, нам легко пройти по дереву со строкой-ключом, посещая только те поддеревья, строки которых не превышают заданного расстояния Хэмминга до ключа. Это возможно потому, что одинаковые подстроки строк, находящихся в дереве, сжаты в одну ветку.