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

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

Задачка для PATRICIA trie.

V>Вроде бы на форуме мелькало, но с ходу найти не получается. Задача кажется не сложной. Может быть, туплю. Если кто-то в теме, просьба подсказать куда копать? Желательно как можно проще. Еще лучше если можно будет быстренько "наложить" на STL.

https://github.com/uxn/patl/tree/vc12
Моя либа, самый свежий публичный вариант. Там есть patl::hamming_distance, пример использования в demos/insider. Для битовых строк понадобится примерно такой компаратор:

using bit_string = std::bitset<BIT_LENGTH>;

namespace uxn { namespace patl {

template <>
class bit_comparator<bit_string, 0>
{
    typedef bit_string value_type;

public:
    typedef bool char_type;

    static const word_t bit_size = 1;

    word_t bit_length(const value_type &v) const
    {
        return v.size();
    }

    word_t get_bit(const value_type &v, word_t id) const
    {
        return v.test(id) ? 1 : 0;
    }

    word_t bit_mismatch(const value_type &a, const value_type &b, word_t skip = 0) const
    {
        if (&a == &b)
            return ~word_t(0);
        for (auto i{skip}; i != a.size(); ++i)
        {
            if (a.test(i) != b.test(i))
                return i;
        }
        return ~word_t(0);
    }
};

} } // uxn::patl