Як реалізувати наївний пошук підрядка?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Наївний пошук підрядка: послідовно перевіряємо кожну позицію i в тексті (0..n−m), посимвольно порівнюючи шаблон довжини m із текстом. При повному збігу повертаємо індекс i (або накопичуємо всі i), при незбігу зсуваємося на 1. Часова складність: найгірша O(n·m), найкраща O(n) (за ранніх незбігів), пам'ять O(1).

Детальний розбір

Ідея алгоритму

Перебрати всі зсуви i від 0 до n−m.
Для кожного i порівняти символи pattern[0..m−1] з text[i..i+m−1].
Якщо всі m символів збіглися, знайшли входження.
Інакше збільшити i на 1 і повторити.
Межі: якщо m = 0, повернути 0 (або всі індекси за умовою задачі); якщо m > n, збігів немає.

Псевдокод

function naiveSearch(text, pattern):
    n = length(text)
    m = length(pattern)
    if m == 0:
        return 0
    if m > n:
        return -1
    for i from 0 to n - m:
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            return i
    return -1

Реалізація

JavaScript

function naiveSearch(text, pattern, all = false) {
  const n = text.length;
  const m = pattern.length;
  if (m === 0) return all ? [...Array(n + 1).keys()] : 0;
  if (m > n) return all ? [] : -1;

  const results = [];
  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && text[i + j] === pattern[j]) j++;
    if (j === m) {
      if (!all) return i;
      results.push(i);
    }
  }
  return all ? results : -1;
}

// Приклади:
// naiveSearch("abracadabra", "abra") -> 0
// naiveSearch("abracadabra", "abra", true) -> [0, 7]
// naiveSearch("aaaaa", "aa", true) -> [0, 1, 2, 3]

Python

def naive_search(text: str, pattern: str, all: bool = False):
    n, m = len(text), len(pattern)
    if m == 0:
        return list(range(n + 1)) if all else 0
    if m > n:
        return [] if all else -1

    found = []
    for i in range(n - m + 1):
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:
            if not all:
                return i
            found.append(i)
    return found if all else -1

# Приклади використання:
# naive_search("abracadabra", "abra") -> 0
# naive_search("abracadabra", "abra", all=True) -> [0, 7]
# naive_search("aaaaa", "aa", all=True) -> [0, 1, 2, 3]

Приклад (покроково)

Нехай text = "ababa", pattern = "aba".

i = 0: порівнюємо "aba" з text[0..2] = "aba", усі 3 символи збіглися, входження на 0.
i = 1: порівнюємо pattern[0] = 'a' з text[1] = 'b', незбіг, зсув.
i = 2: порівнюємо text[2..4] = "aba", збіг, входження на 2 (якщо збираємо всі входження).

Складність

Час: найгірший випадок O(n·m) (наприклад, text = "aaaaa…a", pattern = "aaaab").
Найкращий випадок: O(n) за ранніх незбігів (наприклад, перший символ шаблону рідко трапляється).
Середній: на випадкових даних часто близько до O(n), але теоретичної гарантії немає.
Пам'ять: O(1).

Крайні випадки й коректність

Порожній шаблон: за угодою повернути 0 (або всі індекси 0..n, якщо шукаємо всі).
Шаблон довший за текст: збігів немає.
Перекривні входження: наївний алгоритм коректно знаходить їх, якщо перевіряти кожну позицію i (див. приклад із "aaaaa" і "aa").
Коректність: інваріант - на початку перевірки позиції i вже доведено, що жодна позиція < i не може бути початком збігу (вона перевірена повністю).

Коли використовувати й альтернативи

Використовувати: короткі рядки, одноразовий пошук, простота важливіша за швидкість, обмежені ресурси.
Не використовувати: великі тексти або багаторазові пошуки, краще KMP (O(n+m)), Бойєр-Мур/Хорспул (гарна практика на великих алфавітах), Рабін-Карп (пошук множини шаблонів із хешами).

Типові питання на співбесіді

Як обробляти порожній шаблон і Unicode-графеми?
Як знайти всі входження, включно з перекривними?
Чому найгірша складність O(n·m) і які входи її досягають?
Чим наївний підхід відрізняється від KMP/Бойєра-Мура?

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.