1

文字列「text」、キャレット位置「caret」があり、現在の単語（スペースで区切られている）を見つけたいとします。

私が現在行っている方法は非効率的で、誰かが効率的な方法を持っているかどうか疑問に思っていましたか?

const char* text;
int caret;
int initpos;
int start;
int count = 0;
char word[256];

// text and caret values assigned here.

initpos = caret;
while(caret > 0 && text[caret] != ' ') // get start
{
    caret--;
    count++;
}
start = caret;
caret = initpos;

while(text[caret] && text[caret] != ' ') // get end
{
    caret++;
    count++;
}

word = strsub(text, start, count);
4

3 に答える 3

5

「効率が悪いように見える」とは、コードが効率が悪いように見えるということですか、それとも測定した結果、目的に対して遅すぎることが判明したということですか?

メソッドは O( n ) ステップかかります。ここで、nは入力内の最長の単語の長さです。単語が DNA ストリングのサイズでない限り、これはかなり高速です。

一部のデータセットでは、より高速な方法は、単語の開始位置と終了位置のインデックスを使用することです。間隔を格納する二分探索木はこの法案に適合しますが、O(lg N ) の取得時間が犠牲になります。ここで、Nは入力内の単語の数です。おそらくそれだけの価値はありません。

于 2011-03-04T11:20:56.450 に答える
1

有効な手段だと思います。文字がスペースではないかどうかではなく、文字であるかどうかを確認することをお勧めします。

while(caret > 0 && ((text[caret]>='A' && text[caret]<='Z') || (text[caret]>='a' && text[caret]<='z')))

これは、単語がドット、数字、括弧などで終わっている場合など、他のケースをキャッチします。

于 2011-03-04T12:11:19.980 に答える
0 
#include <ctype.h>

...
// Other definitions from above.
char *p = word;
char *q = text + caret;
while(q >= text && !isblank(*q)) {
   q--;
}
if (q < text) q++; // All non-blanks.
while (*q && !isblank(*q)) {
   *p++ = *q++;
}
*p = '\0';
// word now has nul terminated non-blank characters, p points to EOL or blanks.
于 2011-03-04T11:24:45.120 に答える