c - 从字符数组中获取当前单词的最有效方法

Question

假设我有一个字符串“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);

Answer 1

“看起来效率低下”是指代码对您来说看起来效率低下，还是您已经测量并发现它对您来说太慢了？

您的方法需要 O(n) 步，其中 n 是输入中最长单词的长度。除非你的单词有 DNA 串那么大，否则这已经相当快了。

对于某些数据集，更快的方法是使用单词开始和结束位置的索引。存储间隔的二叉搜索树符合此要求，但代价是 O(lg N) 检索时间，其中 N 是输入中的单词数。可能不值得。