-3

我想知道如何在 C++ 中搜索字符串以查找字符串列表中 ANY 的第一个实例。一种全字版本std::string::find_first_of()：“在字符串中搜索与其参数中指定的任何字符匹配的第一个字符”。

我想要的东西会在字符串中搜索与提供的列表/数组中的任何单词匹配的第一个单词。需要明确的是，我不想在数组中搜索字符串的实例。我想在一个字符串中搜索一个数组中的某个实例。

我的目标是能够取一个句子，并删除列表中的所有单词。例如，如果我给它列表{"the" "brown", "over"}; 和句子"the quick brown fox jumped over the lazy dog"，我希望它输出，" quick fox jumped lazy dog"。如果我愿意，我希望能够给它一个甚至 100 个单词的列表；我需要它是可扩展的。

我能想到的唯一解决方案是在我的文本块上循环使用std::find(stringArray[0])，while并保存找到该单词的索引，然后将所有这些放在另一个for循环中并对数组中的每个单词执行此操作，保存每个单词的索引到一个巨大的列表中。然后可以选择对该列表进行数字排序，最后遍历并删除该列表中某个位置的每个单词。

我真的希望有一个功能或更简单的方法来做到这一点，因为我的解决方案似乎很困难而且很慢，特别是因为我需要在许多不同的字符串上多次使用它来遍历 50,000 个字符的所有句子文本块。任何更好的优化都将是首选。

4

2 回答 2

1

如果您寻找标准函数，如果您敢于将句子存储为字符串容器，则有一些可能性： 

string input="Hello, world ! I whish you all \na happy new year 2016 !";
vector<string> sentence; 

stringstream sst(input);    // split the string into its pieces 
string tmp; 
while (sst>>tmp) 
    sentence.push_back(tmp);

当然，在现实世界中，您不仅可以对空格进行拆分，还可以对标点符号进行拆分。这只是一个概念证明。

一旦以这种形式获得它，就很容易使用以下<algorithm>形式find_first_of()： 

vector<string> search{"We", "You", "I"}; 
auto it =  find_first_of(sentence.begin(), sentence.end(), 
                           search.begin(), search.end()); 

                           // display remaining of the sentence
copy(it , sentence.end(), ostream_iterator<string>(cout,"/"));    
cout<<endl;

并且从向量中删除单词应该不再是一个问题。我把它作为练习交给你。

一旦你有了清理过的向量，你就可以重建一个字符串： 

stringstream so;
copy(it , sentence.end(), ostream_iterator<string>(so," ")); 
string result = so.str();

这里有一个在线演示。

但是，此解决方案不会解决您的所有性能问题。为此，您需要进一步分析性能瓶颈来自何处：您是否制作了大量不必要的对象副本？是不是你自己的算法触发了很多低效的内存分配？还是真的是大量的文字？

进一步工作的一些想法：

  • 为句子中的单词建立一个按字母顺序排列的索引（map> 其中无符号的
  • 考虑一个特里数据结构（特里而不是树！！）
  • 在中使用正则表达式<regex>
于 2016-01-10T02:12:12.623 回答
1

有些人的快别人的慢，所以很难说你指的是哪个快，50000个字符听起来也不大，必须做一些非凡的事情。

唯一应该避免的是就地操作输入字符串（将导致 O(n^2) 运行时间） - 只需返回一个新的结果字符串。为结果字符串保留足够的内存可能是明智的，因为它会为某些输入保存一个常数因子。

有我的提议：

std::string remove_words(const std::string &sentence, const std::set<std::string> &words2remove, const std::string &delimiters){

    std::string result;
    result.reserve(sentence.size());//ensure there is enough place 

    std::string lastDelimiter;//no delimiter so far...
    size_t cur_position=0;
    while(true){
      size_t next=sentence.find_first_of(delimiters, cur_position);
      std::string token=sentence.substr(cur_position, next-cur_position);

      result+=lastDelimiter;
      if(words2remove.find(token)==words2remove.end())
         result+=token;//not forbidden

      if(next==std::string::npos)
        break;

      //prepare for the next iteration:  
      lastDelimiter=sentence[next];
      cur_position=next+1;
    }

    return result;
}

由于查找速度更快，此方法使用一组而不是禁用词列表。作为分隔符，可以使用任何字符集，例如" "或" ,.;"。

它在 O(n*log(k)) 中运行，其中 n 是句子中的字符数，k 是禁止集中的单词数。

如果您需要更灵活的 tokonizer 并且不想重新发明轮子，您可能需要研究boost::tokonizer 。

如果禁用词的数量很大，您可以考虑使用 std::unordered_set (c++11) 或boost::unordered_set代替 std::set 将算法的预期运行时间减少到 O(n) .

于 2016-01-10T13:39:51.920 回答