44

可能不是最有效的方法，但它是否正确且可移植？ 

int are_overlapping(const char *a, const char *b) {
  return (a + strlen(a) == b + strlen(b));
}

澄清一下：我正在寻找的是memory中的重叠，而不是实际内容中的重叠。例如： 

const char a[] = "string";
const char b[] = "another string";
are_overlapping(a, b); // should return 0
are_overlapping(a, a + 3); // should return 1
4

5 回答 5

33

是的，您的代码是正确的。如果两个字符串在样本位置结束，它们根据定义重叠 - 它们共享相同的空终止符。要么两个字符串相同，要么一个是另一个的子字符串。

关于您的程序的一切都是完美定义的行为，因此假设符合标准的编译器，它应该是完全可移植的。

标准中的相关位来自6.5.9 平等运算符（强调我的）：

两个指针比较相等当且仅当两者都是空指针，都是指向同一个对象（包括指向对象的指针和在其开头的子对象）或函数的指针，两者都是指向同一数组最后一个元素的指针object，或者一个是指向一个数组对象末尾的指针，另一个是指向另一个数组对象的开头的指针，该数组对象恰好紧跟在地址空间中的第一个数组对象之后。

于 2013-07-09T23:47:12.957 回答
12

考虑到 zdan 对我之前的帖子的评论（可能很快会被删除），我得出的结论是检查端点就足够了。

如果有任何重叠，空终止符将使两个字符串不不同。让我们看看一些可能性。

如果你从

a 0x10000000 "Hello" and somehow add
b 0x10000004 "World",

你会得到一个单词：HellWorld，因为 W 会覆盖 \0。它们将在同一端点结束。

如果您以某种方式写到相同的起点：

a 0x10000000 "Hello" and
b 0x10000000 "Jupiter"

您将拥有 Jupiter 这个词，并且具有相同的端点。

是否存在您可以拥有相同端点并且没有重叠的情况？有点儿。

a = 0x1000000 "Four" and
b = 0x1000004 "".

这也会产生重叠。

我想不出任何时候你会在没有匹配端点的地方出现重叠 -假设你正在将空终止的字符串写入内存。

所以，简短的回答是：是的，你的支票就足够了。

于 2013-07-09T23:47:18.703 回答
2

它可能与您的用例无关，因为您的问题专门针对 C 字符串，但如果数据在字符串中嵌入了 NUL 字节，则代码将不起作用。

char a[] = "abcd\0ABCD";
char *b = a + 5;

除此之外，您的解决方案是直截了当且正确的。它之所以有效，是因为您仅==用于指针比较，并且根据标准（来自 C11 6.5.9/6）

两个指针比较相等当且仅当两者都是空指针，都是指向同一个对象（包括指向对象的指针和在其开头的子对象）或函数的指针，两者都是指向同一数组最后一个元素的指针对象，或者一个是指向一个数组对象末尾的指针，另一个是指向另一个数组对象的开头的指针，该数组对象恰好紧随地址空间中的第一个数组对象。

但是，关系运算符更严格（来自 C11 6.5.8/5）：

比较两个指针时，结果取决于所指向对象在地址空间中的相对位置。如果指向对象类型的两个指针都指向同一个对象，或者都指向同一个数组对象的最后一个元素，它们比较相等。如果指向的对象是同一个聚合对象的成员，则指向稍后声明的结构成员的指针比较大于指向结构中较早声明的成员的指针，并且指向具有较大下标值的数组元素的指针比较大于指向同一数组的元素的指针具有较低的下标值。所有指向同一个联合对象成员的指针比较相等。如果表达式 P 指向一个数组对象的一个​​元素，而表达式 Q 指向同一个数组对象的最后一个元素，

最后一句是踢球者。

有些人对您的代码可能会计算重叠长度两次的事实表示异议，并试图采取预防措施来避免它。然而，减少计算的效率被每次迭代额外的指针比较所抵消，或者涉及未定义或实现定义的行为。假设您想要一个便携且合规的解决方案，实际平均增益可能为零，不值得付出努力。

于 2013-07-10T02:35:25.113 回答
1

这个解决方案仍然是最坏情况下的性能，但针对命中进行了优化——您不必解析两个字符串。

char * temp_a = a;
char * temp_b = b;

while (*temp_a != '\0') {

    if (temp_a++ == b) 
        return 1;

}

// check for b being an empty string
if (temp_a == b) return 1;

/* but if b was larger, we aren't done, so you have to try from b now */
while (*temp_b != '\0') {
    if (temp_b++ == a)
        return 1;
}

/* don't need the a==b check again here

return 0;

显然，只有指针相等（不是不等式）在 C 中是可移植的，因此以下解决方案不可移植——下面的所有内容都是在我知道之前。

您的解决方案是有效的，但为什么要在第二个字符串上计算 strlen 呢？你知道一个字符串的起点和终点，只要看看另一个是否在它们之间（包括）。节省您通过第二个字符串 - O(M+N) 到 O(M)

char * lower_addr_string = a < b ? a : b
char * higher_addr_string = a > b ? a : b
length = strlen(lower_addr_string)
return higher_addr_string >= lower_addr_string && higher_addr_string <= lower_addr_string + length;

或者，自己解析字符串..

char * lower_addr_string = a < b ? a : b
char * higher_addr_string = a > b ? a : b
while(*lower_addr_string != '\0') {
    if (lower_addr_string == higher_addr_string)
        return 1;
    ++lower_addr_string;
}
/* check the last character */
if (lower_addr_string == higher_addr_string)
    return 1;
return 0;
于 2013-07-10T01:38:57.020 回答
1

是的，您的检查是正确的，但它肯定不是最有效的（如果“效率”是指计算效率）。您的实现中明显的直观低效率是基于这样一个事实，即当字符串实际重叠时，strlen调用将迭代它们的公共部分两次。

为了形式上的效率，人们可能会使用一种稍微不同的方法

int are_overlapping(const char *a, const char *b) 
{
  if (a > b) /* or `(uintptr_t) a > (uintptr_t) b`, see note below! */
  {
    const char *t = a; 
    a = b; 
    b = t;
  }

  while (a != b && *a != '\0')
    ++a;

  return a == b;
}

关于这个版本的一个重要说明是，它对两个不能保证指向同一个数组的指针进行关系比较，这在形式上会导致未定义的行为。它将在具有平面内存模型的系统上实际工作，但可能会受到迂腐代码审查者的批评。要正式解决此问题，可以uintptr_t在执行关系比较之前将指针转换为。这样，在大多数（如果不是全部）具有平面内存模型的传统实现中，未定义的行为将转换为具有适当语义的实现定义的行为。

这种方法没有“重复计数”问题：它只分析位于内存中“较早”的字符串的非重叠部分。当然，在实践中，这种方法的好处可能被证明是不存在的。这将取决于您的strlen实现质量和实际输入的属性之一。

例如，在这种情况下

const char *str = "Very very very long string, say 64K characters long......";

are_overlapped(str, str + 1);

我的版本将比您的版本更快地检测到重叠。我的版本将在循环的 1 次迭代中执行此操作，而您的版本将花费 2 * 64K 次迭代（假设 的简单实现strlen）。

如果您决定深入到有问题的指针比较领域，上述想法也可以重新实现为

int are_overlapping(const char *a, const char *b) 
{
  if (a > b)
  {
    const char *t = a; 
    a = b; 
    b = t;
  }

  return b <= a + strlen(a);
}

此实现不会在每次迭代时执行额外的指针比较。我们为此付出的代价是它总是迭代到其中一个字符串的末尾，而不是提前终止。然而，它仍然比您的实现更有效，因为它只调用strlen一次。

于 2013-07-10T01:43:32.997 回答