Решение проблемы со строками

Question

Дано множество S = {s ₁ , ..., s _m }, где каждый s _i - строка длины k надалфавит {0,1,?}.

Я ищу эффективный алгоритм, решающий следующую задачу решения:
Верно ли, что для каждого 1 ≤ a i s _i (a) = 0 и s _i (b) = 1 или s _i (a) = 1 и s _i (b) = 0, где s _i (a) обозначает a-й символ в строке s _i .

Я ищу алгоритм сублинейного времени вm, так что целью будет что-то вроде O (\ sqrt (m) f (k)).

Answer 1

Не может быть сделано менее чем за линейное время, если не разрешена предварительная автономная обработка.

По сути, первая строка, которая удовлетворяет вашему критерию, будет последней из рассмотренных вами.И вам, возможно, придется сначала рассмотреть все другие m-1.

Answer 2

Легко.Битовое поле вашего символьного пространства (0 == 0x1, 1 == 0x2, ...), затем взять первые N символов каждой строки в S и добавить их преобразованные представления, XOR всегопротив 0x3,..., и посмотрите, оценивает ли он ноль.

Для более быстрого обхода, чем O(n), используйте это для формирования двоичного дерева поиска или кучи (O(lg n) fetch) или хэша (O(1)выборки).Если гарантируется сортировка S , это станет еще проще.

По крайней мере, если я правильно понимаю ваш вопрос.Для лучшего, более теоретического результата с ограниченной математической сложностью и доказательствами Math.SE или CSTheory.SE являются точками доступа.