Z-функция деген не?

Z-функция — s строкасы үшін z массиві.

z[i] — i позициясынан басталатын suffix пен бүкіл строканың prefix-і қанша символға дейін совпадает ететінін көрсетеді.

Әдетте:

z[0] = 0

Қарапайым мысал

Строка:

aaaaa

Әр позицияны қарайық:

i = 1: aaaa prefix aaaa-пен совпадает → z[1] = 4
i = 2: aaa prefix aaa-пен совпадает → z[2] = 3
i = 3: aa prefix aa-пен совпадает → z[3] = 2
i = 4: a prefix a-пен совпадает → z[4] = 1

Сондықтан:

s:  a a a a a
i:  0 1 2 3 4
z:  0 4 3 2 1

Тағы бір мысал

Строка:

abacaba

Z-функция:

s:  a b a c a b a
i:  0 1 2 3 4 5 6
z:  0 0 1 0 3 0 1

Неге z[4] = 3?

s[4...] = aba
prefix = aba

3 символ совпало

Prefix function-нан айырмашылығы

Наивный әдіс

Әр i позициясы үшін символдарды string басымен жай салыстыруға болады.

vector<int> z_function_slow(string s) {
    int n = s.size();

    vector<int> z(n);

    for (int i = 1; i < n; i++) {
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
            z[i]++;
        }
    }

    return z;
}

Бірақ бұл әдіс ең жаман жағдайда:

Жылдам алгоритм идеясы

Жылдам алгоритм [l, r] отрезогын сақтайды.

Бұл — prefix-пен уже совпадает етіп тұрған ең оң жақтағы segment.

z[i] санағанда, егер i осы [l, r] ішінде болса, дайын ақпаратты қолданамыз.

Егер i [l, r] сыртында болса

Егер:

i > r

Бұл позиция туралы ештеңе білмейміз. Сондықтан нөлден бастап салыстырамыз:

while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
    z[i]++;
}

Егер жақсы совпадение шықса, [l, r] жаңартамыз.

Егер i [l, r] ішінде болса

Егер:

i <= r

Онда жауаптың бір бөлігін бұрынғы мәннен аламыз.

i позициясы [l, r] ішінде тұр. Оған prefix жағында сәйкес позиция:

i - l

Сондықтан бастапқы мән:

z[i] = min(r - i + 1, z[i - l]);

Z-функцияның негізгі коды

vector<int> z_function(string s) {
    int n = s.size();

    vector<int> z(n);

    int l = 0;
    int r = 0;

    for (int 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) {
            l = i;
            r = i + z[i] - 1;
        }
    }

    return z;
}

Толық программа

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

vector<int> z_function(string s) {
    int n = s.size();

    vector<int> z(n);

    int l = 0;
    int r = 0;

    for (int 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) {
            l = i;
            r = i + z[i] - 1;
        }
    }

    return z;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;

    vector<int> z = z_function(s);

    for (int x : z) {
        cout << x << ' ';
    }

    return 0;
}

Input / Output

Input

abacaba

Output

0 0 1 0 3 0 1

l және r айнымалылары

[l, r] — prefix-пен совпадает етіп тұрған ең оң жақтағы табылған отрезок.

Мысалы:

s = abacaba

i = 4 позициясында совпадение бар:

s[4...6] = aba
s[0...2] = aba

Онда:

l = 4
r = 6

Неге алгоритм O(n)?

Код ішінде while бар, бірақ ол суммарно O(n) ғана жұмыс істейді.

Әр успешный comparison кезінде z[i] өседі, және оң шекара r оңға жылжиды.

Z-функция арқылы substring іздеу

pattern строкасының text ішіндегі барлық occurrence-ын табу керек.

Жаңа string құрамыз:

pattern + "#" + text

Кейін Z-функция санаймыз.

# символы pattern және text ішінде кездеспеуі керек.

Код: substring search

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

vector<int> z_function(string s) {
    int n = s.size();

    vector<int> z(n);

    int l = 0;
    int r = 0;

    for (int 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) {
            l = i;
            r = i + z[i] - 1;
        }
    }

    return z;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string pattern, text;

    cin >> pattern >> text;

    string s = pattern + "#" + text;

    vector<int> z = z_function(s);

    int m = pattern.size();

    for (int i = m + 1; i < (int)s.size(); i++) {
        if (z[i] == m) {
            cout << i - m - 1 << ' ';
        }
    }

    return 0;
}

Іздеу мысалы

Input

aba
abacaba

Output

0 4

Себебі aba строкасы abacaba ішінде мына позицияларда кездеседі:

0 және 4

Неге позиция i - m - 1?

Жалпы string:

pattern + "#" + text

Text-тің алдында:

m символ pattern + 1 символ #

Сондықтан жалпы string ішіндегі i позициясы text ішінде мына позицияға сәйкес:

i - m - 1

find_occurrences функциясы

Pattern-нің text ішіндегі барлық позициясын қайтаратын функция:

vector<int> find_occurrences(string pattern, string text) {
    string s = pattern + "#" + text;

    vector<int> z = z_function(s);
    vector<int> ans;

    int m = pattern.size();

    for (int i = m + 1; i < (int)s.size(); i++) {
        if (z[i] == m) {
            ans.push_back(i - m - 1);
        }
    }

    return ans;
}

КМП-пен салыстыру

String барлық border-лерін табу

Border — string-тің бір уақытта prefix және suffix болатын бөлігі, бірақ ол бүкіл string-тің өзі болмауы керек.

Z-функция арқылы барлық border ұзындықтарын табуға болады.

Егер:

i + z[i] == n

Онда i позициясынан басталатын suffix prefix-пен z[i] ұзындыққа совпало.

Код: барлық border Z-функция арқылы

vector<int> get_borders(string s) {
    int n = s.size();

    vector<int> z = z_function(s);
    vector<int> borders;

    for (int i = 1; i < n; i++) {
        if (i + z[i] == n) {
            borders.push_back(z[i]);
        }
    }

    sort(borders.begin(), borders.end());

    return borders;
}

Border мысалы

Input

ababa

Z-функция:

0 0 3 0 1

Border ұзындықтары:

1 3

Бұл string-тер:

a
aba

String минимальный периоды

Period — string-ті толық құрайтын қайталанатын block ұзындығы.

Мысалы:

ababab

Минимальный period:

2

Себебі:

ab ab ab

Period Z-функция арқылы

Period ұзындығы p бола ала ма деп тексереміз. Егер p позициясынан басталған suffix prefix-пен n - p ұзындыққа совпалса, онда p period болуы мүмкін.

Шарт:

z[p] >= n - p

Тағы керек:

n % p == 0

Код: минимальный period Z арқылы

int minimal_period(string s) {
    int n = s.size();

    vector<int> z = z_function(s);

    for (int p = 1; p <= n; p++) {
        if (n % p == 0 && p < n && z[p] >= n - p) {
            return p;
        }
    }

    return n;
}

Әр prefix қанша рет кездеседі?

Z-функция string prefix-і қай позицияларда кездесетінін көрсетеді.

Егер z[i] = len, онда i позициясында мына prefix ұзындықтары кездеседі:

1, 2, 3, ..., len

Жылдам санау үшін difference array қолданамыз.

Код: әр prefix неше рет кездеседі

vector<int> count_prefixes(string s) {
    int n = s.size();

    vector<int> z = z_function(s);
    vector<int> diff(n + 2);

    for (int i = 1; i < n; i++) {
        if (z[i] > 0) {
            diff[1]++;
            diff[z[i] + 1]--;
        }
    }

    vector<int> cnt(n + 1);

    for (int len = 1; len <= n; len++) {
        cnt[len] = cnt[len - 1] + diff[len];
    }

    for (int len = 1; len <= n; len++) {
        cnt[len]++;
    }

    return cnt;
}

Асимптотика

Z-функция қашан қолданылады?

Типтік қателер

• z[i] prefix function сияқты s[0...i] үшін саналады деп ойлау
• z[i] s[i...] мен бүкіл string prefix-ін салыстыратынын ұмыту
• z[i] = min(r - i + 1, z[i - l]) формуласынан қателесу
• l және r жаңартуды ұмыту
• pattern немесе text ішінде кездесетін separator қолдану
• i - m - 1 позиция формуласынан қателесу
• z[0] = 0 және z[0] = n варианттарын шатастыру
• Period табуда n % p == 0 тексеруді ұмыту

Қысқа шаблон

vector<int> z_function(string s) {
    int n = s.size();

    vector<int> z(n);

    int l = 0;
    int r = 0;

    for (int 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) {
            l = i;
            r = i + z[i] - 1;
        }
    }

    return z;
}

Қысқа pattern search шаблоны

vector<int> find_occurrences(string pattern, string text) {
    string s = pattern + "#" + text;

    vector<int> z = z_function(s);
    vector<int> ans;

    int m = pattern.size();

    for (int i = m + 1; i < (int)s.size(); i++) {
        if (z[i] == m) {
            ans.push_back(i - m - 1);
        }
    }

    return ans;
}

Ең бастысы