Как запустить алгоритм поиска строки по всему тексту

Question

Как запустить алгоритм поиска строки по всему тексту

Я использую алгоритм поиска строки грубой силы для поиска в небольшом предложении, однако я хочу, чтобы алгоритм возвращался каждый раз, когда находит определенную строку, а не находил ее один раз, а затем останавливал

//Declare and initialise variables
string pat, text;

text = "This is a test sentence, find test within this string";

cout << text << endl;

//User input for pat
cout << "Please enter the string you want to search for" << endl;
cin >> pat;

//Set the length of the pat and text
int patLength = pat.size();
int textLength = text.size();

//Algorithm
for (int i = 0; i < textLength - patLength; ++i)
{
//Do while loop to run through the whole text
do
{
int j;

for (j = 0; j < patLength; j++)
{
if (text[i + j] != pat[j])
break; // Doesn't match here.
}

if (j == patLength)
{
finds.push(i); // Matched here.
}
} while (i < textLength);
}

//Print output
cout << "String: " << pat << " was found at positions: " << finds.top();

Программа сохраняет каждую находку в очереди. Когда я запускаю эту программу, она запрашивает ‘pat’, а затем ничего не делает. Я сделал немного отладки и обнаружил, что это, вероятно, цикл do while. Однако я не могу найти решение

0

c++string-search

Решение

Другие решения

Мой первый совет — структурировать ваш код в отдельные функции.

Допустим, у вас есть функция, которая возвращает позицию первого вхождения шаблона в последовательности символов:

using position = typename std::string::const_iterator;
position first_occurrence(position text_begin, position text_end, const std::string& pattern);

Если шаблон больше не встречается, он возвращает text_end,

Теперь вы можете написать очень простой цикл:

auto occurrence = first_occurrence(text_begin, pattern);
while (occurrence != text_end) {
occurrences.push_back(occurrence);
occurrence = first_occurence(occurrence + 1, text_end, pattern);
}

накапливать все вхождения шаблона.

first_occurrence функция уже существует в стандартной библиотеке под именем std::search, Начиная с C ++ 17, вы можете настроить эту функцию с помощью поиска по шаблону в специализированных поисковиках, таких как std::boyer_moore_searcher: он предварительно обрабатывает шаблон, чтобы ускорить его поиск в строке. Вот пример приложения к вашей проблеме:

#include <algorithm>
#include <string>
#include <vector>
#include <functional>

using occurrence = typename std::string::const_iterator;

std::vector<occurrence> find_occurrences(const std::string& input, const std::string& pattern) {
auto engine = std::boyer_moore_searcher(pattern.begin(), pattern.end());
std::vector<occurrence> occurrences;
auto it = std::search(input.begin(), input.end(), engine);
while (it != input.end()) {
occurrences.push_back(it);
it = std::search(std::next(it), input.end(), engine);
}
return occurrences;
}

#include <iostream>

int main() {
std::string text = "This is a test sentence, find test within this string";
std::string pattern = "st";
auto occs = find_occurrences(text, pattern);
for (auto occ: occs) std::cout << std::string(occ, std::next(occ, pattern.size())) << std::endl;
}

0

Источник

Accepted Answer

Вы могли бы использовать std::string::find Функция в сочетании с функцией, которую вы вызываете для каждой находки.

#include <iostream>
#include <functional>
#include <vector>
#include <sstream>

void Algorithm(
const std::string& text, const std::string& pat,
std::function<void(const std::string&,size_t)> f, std::vector<size_t>& positions)
{
size_t pos=0;
while((pos=text.find(pat, pos)) != std::string::npos) {
// store the position
positions.push_back(pos);
// call the supplied function
f(text, pos++);
}
}

// function to call for each position in which the pattern is found
void gotit(const std::string& found_in, size_t pos) {
std::cout << "Found in \"" << found_in << "\" @ " << pos << "\n";
}

int main(int argc, char* argv[]) {
std::vector<std::string> args(argv+1, argv+argc);

if(args.size()==0)
args.push_back("This is a test sentence, find test within this string");

for(const auto& text : args) {
std::vector<size_t> found_at;
std::cout << "Please enter the string you want to search for: ";
std::string pat;
std::cin >> pat;

Algorithm(text, pat, gotit, found_at);

std::cout << "collected positions:\n";
for(size_t pos : found_at) {
std::cout << pos << "\n";
}
}
}

0