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

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

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

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

---

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

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

需要一个更有趣的解决方案来计算具有自我别名的单词：例如，计算"aaaa"字符串中的"aa" 。 如果你需要返回3这种情况，你需要更先进的算法。

---

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

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

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

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

---

除非你的系统有不好的字符串函数实现，否则这应该是最快的：

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

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

链接地址: http://www.djcxy.com/p/85035.html

上一篇: Fastest way to count the number of occurrences of a string

下一篇: What are good test cases for benchmarking & stress testing substring search algorithms?