Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Як реалізувати наївний пошук підрядка?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

Наївний пошук підрядка: послідовно перевіряємо кожну позицію 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/Бойєра-Мура?

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати633 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.