计算字符串出现次数的最快方法

我想知道在另一个字符串（干草堆）中计算字符串（针）出现次数的最快方法是什么。我这样做的方式是：计算字符串出现次数的最快方法

int findWord(char * file, char * word){ 
char *fptr; 
char * current = strtok_r(file, " ,.\n", &fptr); 
int sum = 0; 
while (current != NULL){ 
    //printf("%s\n", current); 
    if(strcmp(current, word) == 0) 
     sum+=1; 
    current = strtok_r(NULL, " ,.\n", &fptr); 
} 
return sum; 
}

使用更复杂的算法（Boyer-Moore）会更快吗？谢谢

来源

2012-05-12 pretobomba

目前，如果您的程序正在计算单词"blah"并遇到令牌"blahblah"，则算法会将其计为零次出现次数。如果需要将其计为两个，则可以使用更高级的方法。

如果你的程序做了你想做的事，你可以尽可能快地进行处理：它已经与较长的“单词”的字母数量成线性关系，所以你无法进一步加速它。

需要一个更有趣的解决方案来计算具有自锯齿功能的字：例如，在"aaaa"字符串内计数"aa" s。如果你需要返回3这种情况，你需要更多更先进的算法。

来源

2012-05-12 10:35:56 dasblinkenlight

使用更复杂的算法（Boyer-Moore）会更快吗？

在你的算法中，比较的单位是一个单词而不是一个字符。这使算法可以忽略跨越字边界的匹配，从而使其在O(n)时间内运行。

我怀疑你会渐渐地击败那个。

至于降低乘法常数，现在你的算法会查看file中的每个字符两次。您可以通过重写代码来使用一对指针和一个单独的for循环来消除冗余（查明详细信息留给读者作为练习:)）

来源

2012-05-12 10:36:31 NPE

除非您的系统有错误的字符串函数实现，这应该是最快的：

const char *s, *t; 
size_t cnt; 
for (cnt=0, s=haystack; t=strchr(s, needle); s=t+1, cnt++);

如果您不想计算重叠匹配，请稍微调整一下（+ strlen（针）而不是+1）。

来源

2012-05-12 12:15:50

计算字符串出现次数的最快方法

回答

相关问题