Поиск строки — это фундаментальная операция в программировании, которая включает в себя поиск вхождения или положения определенной подстроки в более крупной строке. В этой статье блога мы рассмотрим несколько распространенных методов поиска строк, а также примеры кода на разных языках программирования. Независимо от того, являетесь ли вы новичком или опытным программистом, эта статья предоставит вам полный обзор различных методов поиска строк.

1. Наивный поиск строк.
   Алгоритм наивного поиска строк — это самый простой и понятный подход. Он включает в себя проверку каждого символа строки на соответствие шаблону поиска. Вот пример того, как простой поиск строк может быть реализован в Python:

def naive_string_search(text, pattern):
    occurrences = []
    for i in range(len(text) - len(pattern) + 1):
        j = 0
        while j < len(pattern) and text[i + j] == pattern[j]:
            j += 1
        if j == len(pattern):
            occurrences.append(i)
    return occurrences

2. Алгоритм Кнута-Морриса-Пратта (KMP):
   Алгоритм KMP представляет собой эффективный алгоритм поиска строк, который позволяет избежать ненужных сравнений символов за счет использования предварительно вычисленной таблицы соответствия шаблону. Он обеспечивает линейную временную сложность для поиска строк. Вот пример того, как алгоритм KMP может быть реализован на Java:

public class KMPAlgorithm {
    public static List<Integer> search(String text, String pattern) {
        List<Integer> occurrences = new ArrayList<>();
        int[] lps = computeLPS(pattern);
        int i = 0, j = 0;
        while (i < text.length()) {
            if (text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                if (j == pattern.length()) {
                    occurrences.add(i - j);
                    j = lps[j - 1];
                }
            } else {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return occurrences;
    }
    private static int[] computeLPS(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0;
        int i = 1;
        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
}

3. Алгоритм Бойера-Мура.
   Алгоритм Бойера-Мура — это еще один эффективный алгоритм поиска строк, который использует две эвристики для пропуска сравнений. Он сравнивает шаблон справа налево, позволяя быстрее пропускать ненужные совпадения. Вот пример того, как алгоритм Бойера-Мура можно реализовать на C++:

#include <iostream>
#include <vector>
#include <algorithm>
std::vector<int> boyerMooreSearch(const std::string& text, const std::string& pattern) {
    std::vector<int> occurrences;
    int n = text.length();
    int m = pattern.length();

    std::vector<int> lastOccurrence(256, -1);
    for (int i = 0; i < m; i++) {
        lastOccurrence[pattern[i]] = i;
    }

    int i = m - 1;
    int j = m - 1;
    while (i < n) {
        if (text[i] == pattern[j]) {
            if (j == 0) {
                occurrences.push_back(i);
                i += m;
                j = m - 1;
            } else {
                i--;
                j--;
            }
        } else {
            i += m - std::min(j, 1 + lastOccurrence[text[i]]);
            j = m - 1;
        }
    }

    return occurrences;
}
int main() {
    std::string text = "Lorem ipsum dolor sit amet, consectetur adipiscing elit.";
    std::string pattern = "ipsum";
    std::vector<int> occurrences = boyerMooreSearch(text, pattern);
    std::cout << "Occurrences: ";
    for (int occurrence : occurrences) {
        std::cout << occurrence << " ";
    }
    std::cout << std::endl;
    return 0;
}

В этой статье мы рассмотрели три распространенных метода поиска строк: простой поиск строк, алгоритм Кнута-Морриса-Пратта и алгоритм Бойера-Мура. Каждый метод имеет свои преимущества и подходит для разных сценариев. Понимая эти методы, вы сможете эффективно выполнять операции поиска строк в своих задачах программирования.