3

別の文字列 (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) を使用した方が速いでしょうか? ありがとう

4

3 に答える 3

2

現在、プログラムが単語"blah"をカウントしていて、トークンがであることに遭遇した"blahblah"場合、アルゴリズムはそれをゼロオカレンスとしてカウントします。2つとして数える必要がある場合は、より高度なアプローチの恩恵を受けることができます。

プログラムが希望どおりに動作する場合は、可能な限り高速に処理しています。長い「単語」の文字数はすでに線形であるため、これ以上高速化することはできません。

自己エイリアシングを使用して単語をカウントするには、さらに興味深いソリューションが必要になります。たとえば、文字列"aa"内のsをカウントし"aaaa"ます。この状況に戻る必要が3ある場合は、はるかに高度なアルゴリズムが必要になります。

于 2012-05-12T10:35:56.753 に答える
1

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

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

あなたがそれを漸近的に打ち負かすことができるとは思えません。

乗法定数を下げる限り、現在、アルゴリズムはすべての文字をfile2回調べます。ポインターのペアと単一の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++);

重複する一致をカウントしたくない場合は、少し調整します (+1 ではなく +strlen(needle))。

于 2012-05-12T12:15:50.457 に答える