Z-функция

Поиск всех вхождений подстроки в строку за O(n + m)

🐍 Python

def z_function(s):
    n = len(s)
    Z = [0] * n
    l = 0
    r = 0
    for i in range(1, n):
        if i <= r:
            Z[i] = min(r - i + 1, Z[i - l])
        while i + Z[i] < n and s[Z[i]] == s[i + Z[i]]:
            Z[i] += 1
        if i + Z[i] - 1 > r:
            l = i
            r = i + Z[i] - 1
    return Z

s = input()
p = input()
t = p + '#' + s
Z = z_function(t)
m = len(p)
ANS = [i - m - 1 for i in range(len(t)) if Z[i] == m]
print(len(ANS))
print(*[x + 1 for x in ANS])

⚙️ C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> z_function(const string& s) {
    ll n = s.size();
    vector<ll> Z(n, 0);
    ll l = 0, r = 0;
    for (ll i = 1; i < n; i++) {
        if (i <= r) {
            Z[i] = min(r - i + 1, Z[i - l]);
        }
        while (i + Z[i] < n && s[Z[i]] == s[i + Z[i]]) {
            Z[i]++;
        }
        if (i + Z[i] - 1 > r) {
            r = i + Z[i] - 1;
            l = i;
        }
    }
    return Z;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    string s, p;
    cin >> s >> p;
    
    string t = p + "#" + s;
    vector<ll> Z = z_function(t);
    
    ll m = p.size();
    vector<ll> ans;
    for (ll i = 0; i < (ll)t.size(); i++) {
        if (Z[i] == m) {
            ans.push_back(i - m - 1);
        }
    }
    
    cout << ans.size() << "\n";
    for (ll x : ans) {
        cout << x + 1 << " ";
    }
    
    return 0;
}

Как работает Z-функция?

Z-функция — это массив, где Z[i] равно длине наибольшего общего префикса строки s и её суффикса, начинающегося с позиции i. Алгоритм позволяет эффективно решать задачу поиска подстроки в строке за O(n + m).

Ключевая идея: Строим конкатенированную строку t = p + "#" + s, где # — разделитель, не встречающийся в строках. Затем вычисляем Z-функцию для t. Все позиции, где Z[i] = m (длина образца), соответствуют вхождениям образца в текст.

Алгоритм вычисления Z-функции

l, r — границы текущего отрезка [l, r], для которого известно, что s[l..r] совпадает с префиксом строки
Z[0] обычно равно 0 или длине строки (по определению)
Для i от 1 до n-1:
- Если i внутри текущего отрезка (i ≤ r), то Z[i] ≥ min(r - i + 1, Z[i - l])
- Затем пытаемся увеличить Z[i] прямым сравнением
- Если i + Z[i] - 1 > r, обновляем l и r

Применение для поиска подстроки

Строим t = p + '#' + s
Вычисляем Z-функцию для t
Если Z[i] == |p|, то в позиции i начинается вхождение образца
Позиция в исходном тексте: i - |p| - 1

Временная сложность: O(n + m) — линейный проход по строке.

Пространственная сложность: O(n + m) для хранения массива Z.

Преимущества: Алгоритм очень прост в реализации и работает за линейное время.

Формат ввода и вывода

Ввод:

Первая строка — текст s
Вторая строка — образец p

Вывод:

Первая строка — количество вхождений
Вторая строка — позиции вхождений (1-индексация) в порядке возрастания

Пример ввода:

abacabadabacaba
aba

Вывод:

4
1 5 9 13

Пояснение: образец "aba" встречается в позициях 1, 5, 9, 13 (1-индексация).

Попробовать Z-функцию онлайн

Введите текст и образец для поиска:

Текст s: Образец p: