algorithm - 寻找 n 位字符串的对抗论点

Question

给定：
S，一组奇数个n 位字符串
A，一个特定的 n 位字符串

表明任何决定 A 是否在 S 中的算法都必须在最坏的情况下检查 A 的所有 n 位。

通常，我们当然希望必须查看字符串的所有部分才能进行匹配，但是 S 有一些特殊的东西，它有一个奇怪的大小，这让我无法理解。

Answer 1

假设我们有一个算法 A 可以正确地决定 S 中的成员资格，并说对于任何输入的 n 位字符串，该字符串是否在 S 中。

假设对于给定的输入 n 位字符串 s1，算法 A 从不查看 s1 的位 i 并继续说“s1 在（不在）S 中”。然后一个字符串 s2 等于 s1 除了位 i 翻转也位于（不在）S 中！也就是说，对于我们输入 A 的任何字符串，如果 A 没有查看特定位，那么在 S 中（或不在）S 中还有第二个字符串，该位被翻转。

那么奇数集合 S 有什么特别之处呢？我们不能均匀地配对 S 中的字符串。也就是说，必须有一个字符串 s3，A 查看并确定它在 S 中，对于它没有一个位可以翻转以形成 S 中的另一个字符串。所以 A 必须查看 s3 的所有位（否则我们可以这样一个字符串，就像我们之前做的那样）。

Answer 2

我猜奇数线索是找到你的集合或数组的结尾memory。

假设您使用的是32位系统，也许编译器会将内存中程序的数据结构对齐在八字节边界上。你的数据段中有一大堆字符串指针。如果有奇数个字符串，下一个需要八字节对齐的东西前面有四个字节的填充。如果有偶数个字符串，则没有填充。

Answer 3

如果我理解正确，那么 S 的字符串数是奇数还是偶数都无关紧要。对于 S 中的任何特定字符串，要检查它是否与任意字符串 A 匹配，您必须检查每个字符串中的每个字符。如果其中一个字符串比另一个字符串短或您正在检查的字符不匹配，您可以提前停止。