gpt4 book ai didi

c++ - 我如何有效地在元素之前和之后搜索关键短语

转载 作者:行者123 更新时间:2023-11-28 07:22:20 26 4
gpt4 key购买 nike

我有一个非常大的数据集(范围从 100,000 个元素到 250,000 个元素),我目前将数据存储在一个 vector 中,目的是搜索一组单词。给定一个短语(例如“on, para”),该函数应找到以给定短语开头的所有单词并将所有匹配项推送到队列中。

为了找到第一个词,我使用了二分查找法,这似乎很有效,但在找到第一个词后我就卡住了。我应该如何有效地在元素前后迭代以找到所有相似的词?输入按字母顺序排列,所以我知道所有其他可能的匹配项将在返回的元素之前或之后发生。我觉得也许 <algorithm> 中一定有一个函数我可以利用。以下是相关代码的一部分:

二分查找函数:

int search(std::vector<std::string>& dict, std::string in)
{
//for each element in the input vector
//find all possible word matches and push onto the queue
int first=0, last= dict.size() -1;
while(first <= last)
{
int middle = (first+last)/2;
std::string sub = (dict.at(middle)).substr(0,in.length());
int comp = in.compare(sub);
//if comp returns 0(found word matching case)
if(comp == 0) {
return middle;
}
//if not, take top half
else if (comp > 0)
first = middle + 1;
//else go with the lower half
else
last = middle - 1;
}
//word not found... return failure
return -1;
}

main()

//for each element in our "find word" vector
for (int i = 0; i < input.size()-1; i++)
{
// currently just finds initial word and displays
int key = search(dictionary, input.at(i));
std::cout << "search found " << dictionary.at(key) <<
"at key location " << key << std::endl;
}

最佳答案

std::lower_bound 和向前迭代(你也可以使用 std::upper_bound):

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
typedef std::vector<std::string> Dictionary;
Dictionary dictionary = {
"A", "AA", "B", "BB", "C", "CC"
};
std::string prefix("B");
Dictionary::const_iterator pos = std::lower_bound(
dictionary.begin(),
dictionary.end(),
prefix);
for( ; pos != dictionary.end(); ++pos) {
if(pos->compare(0, prefix.size(), prefix) == 0) {
std::cout << "Match: " << *pos << std::endl;
}
else break;
}
return 0;
}

关于c++ - 我如何有效地在元素之前和之后搜索关键短语,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19230612/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com