文字列の出現数を数える最も速い方法

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"である場合、アルゴリズムではゼロ発生としてカウントされます。それを2つと数える必要がある場合は、coundの方がより高度なアプローチをとっています。

あなたが望むプログラムであれば、できるだけ早く処理しています。長い「単語」の文字数では線形であるため、さらに高速化することはできません。

セルフエイリアシングを使用して単語を数えるには、さらに興味深い解決策が必要です。たとえば、"aaaa"文字列内に"aa"を数えます。このような状況のために3を返す必要がある場合は、もっと高度なアルゴリズムが必要です。

Answer 2

もっと複雑なアルゴリズム（Boyer-Moore）を使用する方が早いでしょうか？

アルゴリズムでは、比較単位は文字ではなく単語です。これにより、アルゴリズムは単語境界にまたがる一致を無視することができるため、O(n)時間に実行されます。

私はあなたがそれを漸近的に打ち負かすことができるとは思わない。

倍率定数を下げる限り、アルゴリズムはfileのすべての文字を2回見ます。ポインタのペアと単一のループを使用するようにコードを書き直すことで、その冗長性を排除することができます（詳細については、読者の練習として残してあります:)）

Answer 3

システムに文字列関数、これはおおよそ最速でなければなりません：あなたは、重複マッチをカウントしたくない場合は

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

は（というよりも、1）+ strlenを（針）を、それを少し調整します。