Аргумент противника для поиска n-битных строк

Question

Дано:
S, набор нечетного числа n-битных строк
А, конкретная n-битная строка

Покажите, что любой алгоритм, который решает, находится ли A в S, должен проверять все n битов A в худшем случае.

Обычно, конечно, мы ожидаем, что нам придется посмотреть на все части строки, чтобы выполнить сопоставление, но есть кое-что особенное в S, имеющем нечетный размер, который ускользает от меня.

Answer 1

Допустим, у нас есть алгоритм A, который правильно определяет членство в S и говорит для любой входной n-битной строки, находится ли строка в S или нет.

Предположим, что для данной входной n-битной строки s1 алгоритм A никогда не смотрит на бит i в s1 и продолжает говорить: "s1 находится в (не в) S". Тогда строка s2, равная s1, за исключением перевернутого бита, также находится в (не в) S! То есть для любой строки, которую мы передаем в A, если A не смотрит на конкретный бит, то есть вторая строка также в (или не в) S с перевернутым битом.

Тогда что особенного в множествах нечетного размера S? Мы не можем соединить строки в S равномерно. То есть должна быть строка s3, на которую A смотрит и решает, что она находится в S, для которой нельзя перевернуть ни одного бита, чтобы сформировать другую строку в S. Таким образом, A должен посмотреть на все биты s3 (в противном случае мы могли бы сделать строка, как мы делали раньше).

Answer 2

Я предполагаю, что нечетное число подсказка, чтобы найти конец вашего набора или массива в memory,

Предположим, вы используете 32 Битовая система, возможно, компилятор выравнивает структуры данных вашей программы в памяти по восьмибайтовым границам. В вашем сегменте данных имеется целая загрузка строковых указателей. Если есть нечетное количество строк, следующая вещь, которая требует выравнивания в восемь байтов, имеет четыре байта заполнения перед ней. Если есть четное количество строк, заполнение отсутствует.

Answer 3

Если я правильно понимаю, не имеет значения, имеет ли S нечетное или четное количество строк. Для любой конкретной строки в S, чтобы проверить, что она соответствует произвольной строке A, вы должны проверить каждый символ в каждом. Вы можете остановиться раньше, если одна строка короче другой или проверяемый вами символ не совпадает.