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

Метод 1: Наивный подход
Наивный подход предполагает перебор строки посимвольно и сравнение ее с желаемым шаблоном. Вот пример на Python:

def naive_search(pattern, text):
    m = len(pattern)
    n = len(text)
    for i in range(n - m + 1):
        j = 0
        while j < m:
            if text[i + j] != pattern[j]:
                break
            j += 1
        if j == m:
            return i
    return -1

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

def build_lps(pattern):
    m = len(pattern)
    lps = [0] * m
    length = 0
    i = 1
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps
def kmp_search(pattern, text):
    m = len(pattern)
    n = len(text)
    lps = build_lps(pattern)
    i = 0
    j = 0
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
            if j == m:
                return i - j
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return -1

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

def build_bad_char_table(pattern):
    m = len(pattern)
    bad_char = [-1] * 256
    for i in range(m):
        bad_char[ord(pattern[i])] = i
    return bad_char
def boyer_moore_search(pattern, text):
    m = len(pattern)
    n = len(text)
    bad_char = build_bad_char_table(pattern)
    shift = 0
    while shift <= n - m:
        j = m - 1
        while j >= 0 and pattern[j] == text[shift + j]:
            j -= 1
        if j < 0:
            return shift
        shift += max(1, j - bad_char[ord(text[shift + j])])
    return -1

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

При выборе конкретного метода не забывайте учитывать такие факторы, как длина строки, ожидаемый шаблон и требования к сложности. Приятного кодирования!