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

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

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

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

Пример

Рассмотрим текст: "ababcababcabcabc" и шаблон: "abc"

1. Начните с позиции 0. Сравните «а» с первым символом «а» в образце.
2. Совпадение найдено, переходим к следующим символам: "b" с "b" и "a" с "c".
3. Продолжайте сопоставлять: «b» с «a», «a» с «b» и «b» с «c».
4. Матч не удался на позиции 2.
5. Начните снова с позиции 3. Сравните «а» с первым символом «а» в образце.
6. Успешное совпадение: "a" с "a", "b" с "b" и "c" с "c".
7. Запись позиции 3.

Образец «abc» находится в позициях 0, 6 и 9.

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

#include <iostream>  
#include <string>  
#include <vector>  
  
std::vector<int> stringSearch(const std::string& text, const std::string& pattern) {  
    std::vector<int> positions;  
  
    for(int i = 0; i <= text.length()- pattern.length(); ++i) {  
        int j = 0;  
        while(j < pattern.length() && text[i + j] == pattern[j]) {  
            ++j;  
        }  
        if(j == pattern.length()) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::string text = "ababcababcabcabc";  
    std::string pattern = "abc";  
  
    std::vector<int> result = stringSearch(text, pattern);  
  
    std::cout << "Pattern found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}  

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