Префикс-функция

Префикс деген не?

Префикс — строканың басынан басталатын бөлігі.

Мысалы, строка:

abcde

Оның префикстері:

a
ab
abc
abcd
abcde

Бос строканы да кейде префикс деп санайды, бірақ prefix function ішінде көбіне бос емес префикстер қаралады.

Суффикс деген не?

Суффикс — строканың соңынан аяқталатын бөлігі.

Мысалы, строка:

abcde

Оның суффикстері:

e
de
cde
bcde
abcde

Префикс-функция деген не?

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

pi[i] — s[0...i] строкасының ең ұзын собственный префиксінің ұзындығы, ол осы строканың суффиксіне де тең болуы керек.

s[0...i] подстрокасын аламыз
ең ұзын prefix іздейміз
ол suffix-ке тең болуы керек
бірақ бүкіл строканың өзі болмауы керек

Собственный префикс — бүкіл строкаға тең емес префикс.

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

Строка:

ababa

Толық ababa строкасын қарастырайық.

Оның префикстері:

a
ab
aba
abab
ababa

Оның суффикстері:

a
ba
aba
baba
ababa

Ең ұзын собственный префикс, suffix-ке тең:

aba

Сондықтан соңғы позиция үшін:

pi[4] = 3

pi массивінің мысалы

Строка:

ababa

Префикс-функция:

s:  a b a b a
i:  0 1 2 3 4
pi: 0 0 1 2 3

Түсіндіру:

pi[0] = 0, бір әріпте собственный бос емес prefix жоқ
pi[1] = 0, строка ab, совпадение жоқ
pi[2] = 1, строка aba, a совпадает
pi[3] = 2, строка abab, ab совпадает
pi[4] = 3, строка ababa, aba совпадает

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

Строка:

aaaaa

Префикс-функция:

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

Себебі әр келесі символ совпадение-ді жалғастырады.

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

pi[i] мәнін санағымыз келеді. Алдыңғы позиция үшін мән белгілі болсын:

j = pi[i - 1]

Бұл s[0...i-1] строкасында ұзындығы j совпавший prefix бар деген сөз.

Енді s[i] символын қосамыз.

егер s[i] == s[j], онда совпадение ұзарады
егер s[i] != s[j], онда кішірек prefix-ке откат жасаймыз

Откат деген не?

Егер символдар сәйкес келмесе, тексеруді нөлден бастамаймыз. Біз бұрын есептелген pi мәндерін қолданамыз.

Басында:

j = pi[i - 1]

Егер s[i] != s[j], онда:

j = pi[j - 1]

Бұл келесі кішірек border-ге өтеміз деген сөз.

Дәл осы откаттар алгоритмді жылдам етеді.

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

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

    vector<int> pi(n);

    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];

        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }

        if (s[i] == s[j]) {
            j++;
        }

        pi[i] = j;
    }

    return pi;
}

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

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

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

    vector<int> pi(n);

    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];

        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }

        if (s[i] == s[j]) {
            j++;
        }

        pi[i] = j;
    }

    return pi;
}

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

    string s;
    cin >> s;

    vector<int> pi = prefix_function(s);

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

    return 0;
}

Input / Output

Input

ababa

Output

0 0 1 2 3

Алгоритм жұмысының разборы

Болсын:

s = ababa

Строка бойынша жүреміз:

i = 1, s[i] = b
j = pi[0] = 0
s[1] != s[0]
pi[1] = 0

i = 2, s[i] = a
j = pi[1] = 0
s[2] == s[0]
pi[2] = 1

i = 3, s[i] = b
j = pi[2] = 1
s[3] == s[1]
pi[3] = 2

i = 4, s[i] = a
j = pi[3] = 2
s[4] == s[2]
pi[4] = 3

Откат бар күрделірек мысал

Строка:

abacaba

Префикс-функция:

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

i = 3 позициясында c символы aba prefix-ін жалғастырмайды, сондықтан алгоритм откат жасайды.

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

Ішінде while бар, бірақ ол суммарно O(n²) болмайды.

j айнымалысы әр қадамда тек 1-ге ғана өсе алады, ал откат кезінде pi мәндері бойынша азаяды.

бүкіл алгоритм бойынша j ең көбі n рет өседі
және ең көбі n рет азаяды
сондықтан жалпы уақыт O(n)

Prefix function не үшін керек?

Prefix function string algorithms ішінде көп қолданылады.

1. substring іздеу
2. KMP алгоритмі
3. pattern-нің text ішіндегі барлық occurrence табу
4. string period табу
5. string border-лерімен жұмыс

KMP арқылы substring іздеу

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

Жаңа строка құрамыз:

pattern + "#" + text

# символы екі строкада да кездеспеуі керек.

Егер бір позицияда pi мәні pattern ұзындығына тең болса, онда pattern осы позицияда аяқталды деген сөз.

KMP коды

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

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

    vector<int> pi(n);

    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];

        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }

        if (s[i] == s[j]) {
            j++;
        }

        pi[i] = j;
    }

    return pi;
}

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

    string pattern, text;

    cin >> pattern >> text;

    string s = pattern + "#" + text;

    vector<int> pi = prefix_function(s);

    int m = pattern.size();

    for (int i = 0; i < (int)s.size(); i++) {
        if (pi[i] == m) {
            int pos = i - 2 * m;

            cout << pos << ' ';
        }
    }

    return 0;
}

Мұнда позициялар 0-indexed болып шығарылады.

KMP мысалы

Input

aba
abacaba

Output

0 4

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

0 және 4

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

Біз строка құрамыз:

pattern + "#" + text

Pattern ұзындығы m. Text-тің алдында:

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

Егер жалпы строкада i позициясында ұзындығы m совпадение табылса, онда text ішіндегі басталу позициясы:

i - 2 * m

Строканың border-і

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

Мысалы:

s = ababa

Border-лері:

a
aba

Ең ұзын border ұзындығы:

pi[n - 1]

Барлық border-лерді табу

Бастаймыз:

k = pi[n - 1]

Кейін әр қадамда өтеміз:

k = pi[k - 1]

Осылай барлық border ұзындықтарын табамыз.

Код: string барлық border-лері

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

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

    vector<int> pi(n);

    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];

        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }

        if (s[i] == s[j]) {
            j++;
        }

        pi[i] = j;
    }

    return pi;
}

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

    string s;
    cin >> s;

    vector<int> pi = prefix_function(s);

    vector<int> borders;

    int k = pi[(int)s.size() - 1];

    while (k > 0) {
        borders.push_back(k);
        k = pi[k - 1];
    }

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

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

    return 0;
}

Border мысалы

Input

ababa

Output

1 3

Бұл border ұзындықтары:

a
aba

Строка периоды

Period — строканы толық құрайтын қайталанатын block ұзындығы.

Мысалы:

ababab

Оның периоды:

Себебі:

ab ab ab

Минимальный period prefix function арқылы

Болсын:

n = s.size()
k = pi[n - 1]

Минимальный period-қа кандидат:

period = n - k

Егер n % period == 0, онда бұл шын period. Әйтпесе минимальный period n-ге тең.

Код: string минимальный period

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

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

    vector<int> pi(n);

    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];

        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }

        if (s[i] == s[j]) {
            j++;
        }

        pi[i] = j;
    }

    return pi;
}

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

    string s;
    cin >> s;

    int n = s.size();

    vector<int> pi = prefix_function(s);

    int period = n - pi[n - 1];

    if (n % period == 0) {
        cout << period;
    } else {
        cout << n;
    }

    return 0;
}

Period мысалы

Input

ababab

Output

Строка қайталанудан тұрады:

ab ab ab

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

Кейде әр prefix строка ішінде неше рет кездесетінін табу керек.

Алдымен prefix function санаймыз. Кейін әр pi[i] мәні сәйкес prefix counter-ын арттырады.

Код: prefix occurrence саны

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

    vector<int> pi = prefix_function(s);
    vector<int> cnt(n + 1);

    for (int i = 0; i < n; i++) {
        cnt[pi[i]]++;
    }

    for (int i = n; i > 0; i--) {
        cnt[pi[i - 1]] += cnt[i];
    }

    for (int i = 0; i <= n; i++) {
        cnt[i]++;
    }

    return cnt;
}

cnt[len] — ұзындығы len prefix строка ішінде қанша рет кездесетінін көрсетеді.

Асимптотика

Задача	Уақыт	Память
Префикс-функция	O(n)	O(n)
Pattern-ді text ішінде іздеу	O(n + m)	O(n + m)
Барлық border табу	O(n)	O(n)
Минимальный period	O(n)	O(n)

Prefix function қашан қолданылады?

Задача	Не қолданамыз?
Pattern-ді text ішінде табу	KMP
Барлық border табу	pi[n - 1], кейін откаттар
Минимальный period табу	n - pi[n - 1]
Prefix және suffix совпадение-терімен жұмыс	prefix function

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

Префикс пен суффиксті шатастыру
pi[i] бүкіл string үшін емес, s[0...i] үшін саналатынын ұмыту
pi[0] әрқашан 0 екенін ұмыту
while орнына if жазып, тек бір откат жасау
while ішінде j > 0 шартын ұмыту
KMP ішінде строкаларда кездесетін separator таңдау
KMP позиция индексінен қателесу
0-indexed және 1-indexed позицияларды шатастыру

Қысқа шаблон

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

    vector<int> pi(n);

    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];

        while (j > 0 && s[i] != s[j]) {
            j = pi[j - 1];
        }

        if (s[i] == s[j]) {
            j++;
        }

        pi[i] = j;
    }

    return pi;
}

Ең бастысы

pi[i] = ең ұзын prefix ұзындығы
ол s[0...i] suffix-іне тең
символдар тең болса → j++
тең болмаса → j = pi[j - 1]
prefix function O(n) жұмыс істейді
KMP pattern-ді text ішінде O(n + m) уақытта іздейді