Поиск строки для любого вхождения слова в списке строк
Я хочу знать, как в C ++ искать строку для первого экземпляра ЛЮБОГО списка строк. Этакая версия полного слова 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 символов. блок текста. Все, что лучше оптимизировано, будет предпочтительным.
Решение
Если вы ищете стандартные функции, есть некоторые возможности, если вы решите хранить свои предложения в виде контейнера строк:
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();
Здесь онлайн демо.
Однако это решение не решит все ваши проблемы с производительностью. Для этого вам необходимо проанализировать, откуда возникает ваше узкое место в производительности: вы делаете много ненужных копий объектов? Это то, что ваш собственный алгоритм вызывает много неэффективного распределения памяти? Или это действительно объем текста?
Некоторые идеи для дальнейшей работы:
Другие решения
Пост некоторых людей медленнее других, поэтому трудно сказать который быстро Вы имеете в виду, что 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 если вам нужен более гибкий токонизатор и вы не хотите изобретать велосипед.
Если количество запрещенных слов велико, вы можете использовать std :: unordered_set (c ++ 11) или повышение :: unordered_set вместо std :: set уменьшить ожидаемое время работы алгоритма до O (n).