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

Метод 1: линейный поиск
Метод линейного поиска, также известный как перебор, включает в себя перебор каждого символа целевой строки и сравнение его с нужной подстрокой. Вот пример на Python:

def linear_search(string, substring):
    n = len(string)
    m = len(substring)

    for i in range(n - m + 1):
        j = 0

        while j < m and string[i + j] == substring[j]:
            j += 1

        if j == m:
            return i

    return -1
# Usage
string = "Hello, world!"
substring = "world"
index = linear_search(string, substring)
print("Substring found at index:", index)

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

def kmp_search(string, substring):
    n = len(string)
    m = len(substring)
    lps = compute_lps(substring)

    i = 0
    j = 0

    while i < n:
        if string[i] == substring[j]:
            i += 1
            j += 1

            if j == m:
                return i - j

        elif j > 0:
            j = lps[j - 1]

        else:
            i += 1

    return -1
def compute_lps(substring):
    m = len(substring)
    lps = [0] * m
    length = 0
    i = 1

    while i < m:
        if substring[i] == substring[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

    return lps
# Usage
string = "Hello, world!"
substring = "world"
index = kmp_search(string, substring)
print("Substring found at index:", index)

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

def boyer_moore_search(string, substring):
    n = len(string)
    m = len(substring)
    last_occurrence = generate_last_occurrence(substring)

    i = m - 1
    j = m - 1

    while i < n:
        if string[i] == substring[j]:
            if j == 0:
                return i

            i -= 1
            j -= 1
        else:
            last = last_occurrence.get(string[i], -1)
            i += m - min(j, 1 + last)
            j = m - 1

    return -1
def generate_last_occurrence(substring):
    last_occurrence = {}

    for i, char in enumerate(substring):
        last_occurrence[char] = i

    return last_occurrence
# Usage
string = "Hello, world!"
substring = "world"
index = boyer_moore_search(string, substring)
print("Substring found at index:", index)

Метод 4: регулярные выражения
Регулярные выражения предоставляют мощный и гибкий способ поиска шаблонов в строках. Они предлагают широкий спектр функций для сложного сопоставления строк. Вот пример использования модуля Python re:

import re
def regex_search(string, pattern):
    match = re.search(pattern, string)

    if match:
        return match.start()

    return -1
# Usage
string = "Hello, world!"
pattern = r"world"
index = regex_search(string, pattern)
print("Substring found at index:", index)

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

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