2012-11-20 21 views
-1

出现的所有有找到非const的char *str2的所有出现(包括重叠)char *str1一个高效方式,并输出匹配的数字位置中STR1在C(不是在C++,因为它不同)?Ç找到的子串

+3

您是否需要重叠或不重叠的事件?你知道'strstr()'吗?你有什么尝试? –

+0

这听起来像你需要strstr()。 – imreal

+0

我需要包括重叠和我不知道strstr();) – NGix

回答

0

使用strstr()一个循环中:

int get_substr_count(const char * haystack, const char *needle) 
{ 
    int count = 0; 
    const char *tmp = haystack; 
    while(tmp = strstr(tmp, needle)){ 
     printf("Position: %d\n", (int)(tmp-haystack)); 
     ++count; 
    } 
    return count; 
} 
+0

计数比赛;这与打印比赛的位置不一样。 –

+0

你应该在while循环中递增tmp,否则这段代码会进入无限循环,因为它会继续从同一个索引进行搜索。 – Jignesh

1

你的函数将使用strstr()while循环找到str2的第一场比赛中str1。然后您可以打印该匹配的偏移量。比赛结束后,你会继续搜索第一个字符。当strstr()不再发现匹配时(由strstr()返回NULL表示),您将停止循环。

如果您需要不重叠,您需要知道str2的长度,并且您将开始下一个搜索匹配字符加上str2的长度。

+0

没关系,但我正在寻找更高效的算法,例如后缀数组,因为'str1'可以很长,程序执行时间有限 – NGix

+0

尝试'strstr()';它可能很难被击败。至少在Mac OS X上,我在C中尝试过BM和KMP,并且在性能方面没有接近'strstr()'。我既惊讶又失望。你在ACGTAGGTCA类型字符串上进行'生物信息学'搜索吗? –