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

Question

我想知道计算一个字符串(针)在另一个字符串(haystack)中出现次数的最快方法是什么。我这样做的方式是:

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

Answer 1

目前，如果您的程序正在对单词 "blah" 进行计数，并且遇到标记是 "blahblah"，您的算法会将其计为零次出现。如果需要将其计为两个，您会从更高级的方法中获益。

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

需要一个更有趣的解决方案来计算带有自别名的单词:例如，计算 "aaaa" 字符串中的 "aa"。如果您需要针对这种情况返回 3，则需要更高级的算法。