3

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

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）会更快吗？谢谢

4

3 回答 3

2

目前，如果您的程序正在计算单词"blah"并遇到一个标记 is "blahblah"，您的算法会将其视为零出现。如果需要将其计为两个，您可以从更高级的方法中受益。

如果您的程序执行您想要的操作，那么您将尽可能快地处理：它在较长的“单词”的字母数量上已经是线性的，因此您无法进一步加快它的速度。

需要一个更有趣的解决方案来计算具有自别名的单词：例如，count "aa"s inside "aaaa"string。如果您需要3针对这种情况返回，则需要更高级的算法。

于 2012-05-12T10:35:56.753 回答
1

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

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

我怀疑您是否能够渐近地击败它。

就降低乘法常数而言，现在您的算法会file两次查看每个字符。您可以通过重写代码以使用一对指针和一个for循环来消除这种冗余（弄清楚细节留给读者练习:)）

于 2012-05-12T10:36:31.777 回答
0

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

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

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

于 2012-05-12T12:15:50.457 回答