检测两个字符串之间的重叠长度

Question

int overlap(const char *s1, const char *s2){
    int i = 0;
    while (s1[i] && s2[i] && s1[i] == s2[i])
        i++;
    return i;
}

这将返回作为输入的两个字符串之间子字符串重叠的长度。但是，如果两个字符串是：

abcdefg
1234efg

它返回 0 的重叠，因为它只能读取从字符串开头开始的重叠，有人可以修改或帮助我制作它，以便它可以读取重叠，无论它们在哪里琴弦？

Answer 1

执行此操作的简单方法是为两个字符串构建后缀树（这是使用 麦克雷特）。现在只需查找两个字符串中具有起源的最长公共子字符串。

Answer 2

我认为代码会是这样的：

int overlap(const char *s1, const char *s2){
    int i = 0, n = 0;
    while (s1[i] && s2[i]) {
        if (s1[i++] == s2[i++]) n++;
    }
    return n;
}

Answer 3

好吧，我又想了这个问题。
我认为你希望每个字符串中的相同索引处有重叠。
注意每个字符串末尾的字符“\0”。

所以我们可以编写如下代码：

int overlap(const char *s1, const char *s2){
    int i = 0;
    while (*s1 != '\0' && *s2 != '\0') {
        if (*s1++ == *s2++) i++;
    }
    return i;
}

对于“abcdefg”和“1234efg”，它将返回3。

Answer 4

对我来说看起来有点像家庭作业，是吗？

一旦发现字符串之间存在差异，while 子句就会退出。您必须遍历整个字符串，并且如果 s1[i] == s2[i] 则对每个索引 i 进行计数。

Answer 5

假设您希望每个字符串中的相同索引处重叠，如您的示例所示：

int overlap(const char *s1, const char *s2){
    int length = 0;
    int i = 0;
    while (s1[i] && s2[i] && s1[i] != s2[i])
        i++;
    while (s1[i] && s2[i] && s1[i] == s2[i]) {
        i++;
        length++;
    }
    return length;
}

将达到目的，尽管它不是很优雅。它将找到相同偏移处第一个重叠的长度。

因此，对于 abcdefgh90 和 1234efg890 它将返回 3。

如果您想要匹配字符的总数，请尝试：

int overlap(const char *s1, const char *s2){
    int length = 0;
    int i = 0;
    while (s1[i] && s2[i]) {
        if (s1[i] == s2[i]) {
            length++;
        }
        i++;
    }
    return length;
}

Answer 6

int overlap(const char *s1, const char *s2){
    int k;
    for(k = 0; s1[k] != s2[k]; k++)  // <--- add this loop
      if(0 == s1[k] || 0 == s2[k])
        return 0;
    int i = k;     // initialize to k + 1
    while (s1[i] && s1[i] == s2[i])  // check only s1 (or s2)
        i++;
    return i - k;  // return difference
}