close

Алгоритм текстового поиска (Text Search) в C++ — объяснение, пример и код

Алгоритм текстового поиска является основным методом обработки текста и поиска информации. Этот алгоритм позволяет нам находить и идентифицировать вхождения подстроки(или шаблона) в большом фрагменте текста.

Как это работает

  1. Начните с более крупного фрагмента текста(или документа) и подстроки для поиска.
  2. Итерация через каждый символ текста последовательно.
  3. Сравните подстроку с частью текста той же длины, что и подстрока. Если совпадение найдено, запишите текущую позицию.
  4. Перейдите к следующей позиции и продолжите сравнение.

Пример

Рассмотрим текст: «Давайте найдем подстроку в этом тексте, чтобы увидеть, как работает алгоритм».

И подстрока для поиска: "substring"

  1. Начните с позиции 0. Сравните Let' с «подстрокой». Не совпадает.
  2. Перейти на позицию 1. Сравните et's с "substring". Не совпадает.
  3. Перейти на позицию 2. Сравнить t's " с "substring". Нет совпадений.
  4. Перейти на позицию 3. Сравните 's s с "substring". Не совпадает.
  5. Перейти на позицию 4. Сравните se с "substring". Не совпадает.
  6. Перейти на позицию 5. Сравните sea с "substring". Не совпадает.
  7. Переместитесь на позицию 6. Сравните earc с "substring". Не совпадает.
  8. Перейти на позицию 7. Сравните arch с "substring". Не совпадает.
  9. Перейти к позиции 8. Сравнить rch " с "substring". Нет совпадения.
  10. Перейти на позицию 9. Сравните ch w с "substring". Не совпадает.
  11. Переместитесь на позицию 10. Сравните h wi с "substring". Не совпадает.
  12. Перейти на позицию 11. Сравнить " wit с "substring". Нет совпадения.
  13. Переместитесь на позицию 12. Сравните with с «подстрокой». Не совпадает.
  14. Переместитесь на позицию 13. Сравните ithi с "substring". Не совпадает.
  15. Переместитесь на позицию 14. Сравните thin с "substring". Не совпадает.
  16. Переместитесь на позицию 15. Сравните hinn с "substring". Не совпадает.
  17. Переместитесь на позицию 16. Сравните in t с "substring". Не совпадает.
  18. Переместитесь на позицию 17. Сравните n th с "substring". Не совпадает.
  19. Перейти на позицию 18. Сравнить " thi с "substring". Нет совпадений.
  20. Переместитесь на позицию 19. Сравните this с "substring". Не совпадает.
  21. Перейти на позицию 20. Сравнить his " с "substring". Нет совпадений.
  22. Переместитесь на позицию 21. Сравните is t с "substring". Не совпадает.
  23. Переместитесь на позицию 22. Сравните s te  с "substring". Не совпадает.
  24. Переместитесь на позицию 23. Сравните ubst  с "substring". Не совпадает.
  25. Переместитесь на позицию 24. Сравните bstr с "substring". Не совпадает.
  26. Переместитесь на позицию 25. Сравните stre с "substring". Не совпадает.
  27. Переместитесь на позицию 26. Сравните trin  с "substring". Не совпадает.
  28. Переместитесь на позицию 27. Сравните ring  с "substring". Совпадение найдено, рекордная позиция 27.

Подстрока "substring" находится на позиции 27 в тексте.

Пример кода на С++ 

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> textSearch(const std::string& text, const std::string& query) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- query.length(); ++i) {  
        int j = 0;  
        while(j < query.length() && text[i + j] == query[j]) {  
            ++j;  
        }  
        if(j == query.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "Let's search for a substring within this text to see how the algorithm works.";  
    std::string query = "substring";  
  
    std::vector<int> result = textSearch(text, query);  
  
    std::cout << "Substring found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

В этом примере textSearch функция используется для поиска позиций подстроки «substring» в тексте. Результатом будет вектор, содержащий начальные позиции совпадений.