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

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重叠，因为它只能读取开始在字符串的开始重叠，有人可以修改或帮我做，以便它可以读取重叠没有mantter他们在字符串中？

来源

2011-05-17 Patrick Johnston

这是不小的修改。在这种情况下应该输出什么程序？ s1 = abcdefgh，s2 = 1bc45fgh - 2或3或5？ – 2011-05-17 05:18:30

你必须首先定义你的函数做什么。我发现你想要的和你的代码中有什么不一致。 – shinkou 2011-05-17 05:21:15

'abcdef'和'abcef'怎么样？ – 2011-05-17 05:27:21

嗯，我再次想到了这个问题。我想你想在每个字符串中的相同索引重叠。注意每个字符串末尾的字符'\ 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.

来源

2011-05-17 05:49:09 Yuankun

看起来有点像功课给我，是吗？

您好while子句一旦发现字符串之间的差异就立即退出。你将不得不遍历整个字符串，并且如果s1[i] == s2[i]对于每个索引i都计数。

来源

2011-05-17 05:18:27

假设你想同样的指数在该重叠在每个字符串，如你的例子：

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; 
}

来源

2011-05-17 05:22:16

我认为代码将是这样的：

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; 
}

来源

2011-05-17 05:25:02 Yuankun

有两个i ++ ... – calandoa 2011-05-17 12:56:02

完成此操作的简单方法是为两个字符串构建后缀树（这是使用McCreght完成的）。现在只需在两个字符串中查找具有原点的最长公共子字符串。

来源

2011-05-17 05:46:14

这可能是最合理的表现，但蛮力无疑更容易（约25行off-我认为他的问题域（200字符串，每个50个字符，这里提到：http://stackoverflow.com/questions/6025939/help-with-this-ragged- array-substring-program-in-c），蛮力的表现可能不成问题。 – 2011-05-17 07:51:47

@MichaelBurr问题是如果字符串对齐，如果不是，我不认为有一个更优雅的方式，那么suffixtree。 – 2011-05-17 09:54:00

前缀表或边界表（c.cf Crochemore“字符串算法”）可能会比后缀树简单得多。 – 2012-11-05 12:39:55

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 
}

来源

2011-05-17 06:46:56 iammilind

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

回答

相关问题