КМП алгоритмі

КМП не істейді?

КМП — Кнут-Моррис-Пратт алгоритмі. Ол pattern строкасының text ішінде барлық кездесетін позицияларын табады.

pattern — не іздейміз
text — қай жерден іздейміз
answer — pattern кездесетін позициялар

Мысалы:

pattern = aba
text = abacaba

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

0 4

Наивный поиск

Ең қарапайым әдіс — pattern-ді text-тің әр позициясына қойып көру.

for (int i = 0; i + m <= n; i++) {
    bool ok = true;

    for (int j = 0; j < m; j++) {
        if (text[i + j] != pattern[j]) {
            ok = false;
            break;
        }
    }

    if (ok) {
        cout << i << ' ';
    }
}

Бірақ бұл әдістің уақыты:

O(n * m)

Егер string үлкен болса, бұл баяу болады.

КМП идеясы

КМП қате болған сайын салыстыруды басынан бастамайды. Ол pattern-нің қандай бөлігі уже совпало екенін қолданады.

Ол үшін қолданылады:

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

егер совпадение бұзылса
толық артқа қайтпаймыз
кішірек совпавший prefix-ке откат жасаймыз

Префикс және суффикс

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

abcde

префикстер:
a
ab
abc
abcd
abcde

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

abcde

суффикстер:
e
de
cde
bcde
abcde

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

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

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

Мысал:

s = ababa

pi = 0 0 1 2 3

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

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;
}

КМП prefix function-ды қалай қолданады?

pattern-ді text ішінде табу үшін жаңа string құрамыз:

pattern + "#" + text

# — separator. Ол pattern және text ішінде кездеспеуі керек.

Кейін осы жаңа string үшін prefix function санаймыз.

егер pi[i] == pattern.size()
демек pattern толық совпало
бір occurrence табылды

КМП үшін string мысалы

Болсын:

pattern = aba
text = abacaba

Онда құрамыз:

s = aba#abacaba

Кейін бүкіл s үшін prefix function санаймыз.

Егер бір жерде pi[i] = 3 болса, онда aba осы позицияда аяқталды деген сөз.

Позиция формуласы

Болсын:

m = pattern.size()

Егер жалпы string s = pattern + "#" + text ішінде i позициясында:

pi[i] = m

Онда text ішіндегі басталу позициясы:

pos = i - 2 * m

Бұл кодта позициялар 0-indexed.

Неге pos = i - 2 * m?

Жалпы string былай тұрады:

pattern + "#" + text

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

m символ pattern
1 символ #
барлығы m + 1 символ

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

i - m + 1

Text ішіндегі позицияға өту үшін m + 1 азайтамыз:

(i - m + 1) - (m + 1) = i - 2 * m

КМП коды

#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;
}

Input / Output

Input

aba
abacaba

Output

0 4

Мысалды разбор

Іздейміз:

aba

Мына string ішінде:

abacaba

Қолмен тексерсек:

позиция 0: aba совпало
позиция 1: bac совпало емес
позиция 2: aca совпало емес
позиция 3: cab совпало емес
позиция 4: aba совпало

Answer:

0 4

find_occurrences функциясы

Барлық позицияларды қайтаратын бөлек функция жасау ыңғайлы.

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

    vector<int> pi = prefix_function(s);
    vector<int> ans;

    int m = pattern.size();

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

    return ans;
}

Функциямен толық программа

#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;
}

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

    vector<int> pi = prefix_function(s);
    vector<int> ans;

    int m = pattern.size();

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

    return ans;
}

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

    string pattern, text;

    cin >> pattern >> text;

    vector<int> ans = find_occurrences(pattern, text);

    for (int pos : ans) {
        cout << pos << ' ';
    }

    return 0;
}

Тек бірінші occurrence іздеу

Кейде тек бірінші позиция керек. Егер occurrence жоқ болса, -1 қайтарамыз.

int find_first(string pattern, string 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) {
            return i - 2 * m;
        }
    }

    return -1;
}

pattern text ішінде бар ма?

Егер тек substring бар-жоғын білу керек болса:

bool contains(string pattern, string text) {
    return find_first(pattern, text) != -1;
}

Бұл да жұмыс істейді:

O(n + m)

КМП үлкен string жасамай

pattern + "#" + text құрмай-ақ іздеуге болады. Алдымен prefix function тек pattern үшін саналады.

Кейін text бойынша жүріп, қазіргі совпадение ұзындығын j ұстаймыз.

j — pattern-нің қанша символы қазір совпало
егер text[i] == pattern[j], j өседі
егер j == m, occurrence табылды

Код: КМП склейкасыз

vector<int> kmp_search(string pattern, string text) {
    vector<int> pi = prefix_function(pattern);
    vector<int> ans;

    int n = text.size();
    int m = pattern.size();

    int j = 0;

    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }

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

        if (j == m) {
            ans.push_back(i - m + 1);
            j = pi[j - 1];
        }
    }

    return ans;
}

Бұл вариант қосымша үлкен string құрғың келмесе ыңғайлы.

Толық код: КМП склейкасыз

#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;
}

vector<int> kmp_search(string pattern, string text) {
    vector<int> pi = prefix_function(pattern);
    vector<int> ans;

    int n = text.size();
    int m = pattern.size();

    int j = 0;

    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }

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

        if (j == m) {
            ans.push_back(i - m + 1);
            j = pi[j - 1];
        }
    }

    return ans;
}

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

    string pattern, text;

    cin >> pattern >> text;

    vector<int> ans = kmp_search(pattern, text);

    for (int pos : ans) {
        cout << pos << ' ';
    }

    return 0;
}

Неге occurrence табылғаннан кейін откат жасаймыз?

j == m болғанда pattern толық табылды. Бірақ келесі occurrence қазіргі occurrence-пен пересекаться етуі мүмкін.

Сондықтан жай ғана j = 0 жасау дұрыс емес. Дұрысы:

j = pi[j - 1];

Осылай пересекающиеся occurrence-тер де табылады.

Пересекающиеся occurrence мысалы

Болсын:

pattern = aaa
text = aaaaa

Occurrence-тер:

0 1 2

Олар бір-бірімен пересекаются:

aaa..
.aaa.
..aaa

Сондықтан pattern табылғаннан кейін pi арқылы откат жасаймыз.

КМП арқылы occurrence санын санау

Егер позициялар емес, тек саны керек болса:

int count_occurrences(string pattern, string text) {
    vector<int> ans = kmp_search(pattern, text);

    return ans.size();
}

Немесе цикл ішінде counter-ды бірден арттыруға болады.

Код: тек occurrence саны

int count_occurrences(string pattern, string text) {
    vector<int> pi = prefix_function(pattern);

    int n = text.size();
    int m = pattern.size();

    int j = 0;
    int cnt = 0;

    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }

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

        if (j == m) {
            cnt++;
            j = pi[j - 1];
        }
    }

    return cnt;
}

Наивный поиск пен КМП салыстыру

Метод	Уақыт	Идея
Наивный поиск	O(n * m)	әр позицияны басынан тексереміз
КМП	O(n + m)	prefix function және откат қолданамыз

КМП қашан қолданылады?

pattern-ді text ішінде табу керек
pattern-нің барлық позициясын табу керек
occurrence санын санау керек
string үлкен
guaranteed O(n + m) керек

Асимптотика

Бөлік	Уақыт	Память
prefix_function(pattern)	O(m)	O(m)
text ішінде іздеу	O(n)	O(1), answer-ден басқа
толық КМП	O(n + m)	O(m)
склейкамен вариант	O(n + m)	O(n + m)

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

Позициялар көбіне 0-indexed екенін ұмыту
pattern немесе text ішінде кездесетін separator таңдау
i - 2 * m формуласынан қателесу
Occurrence табылғаннан кейін j = 0 жасап, пересечения жоғалту
Prefix function ішінде while орнына if жазу
while ішінде j > 0 шартын ұмыту
pattern бос болған кезде pattern[j] қолдану
n text ұзындығы және m pattern ұзындығын шатастыру

Қысқа prefix function шаблоны

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;
}

Қысқа КМП шаблоны

vector<int> kmp_search(string pattern, string text) {
    vector<int> pi = prefix_function(pattern);
    vector<int> ans;

    int n = text.size();
    int m = pattern.size();

    int j = 0;

    for (int i = 0; i < n; i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = pi[j - 1];
        }

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

        if (j == m) {
            ans.push_back(i - m + 1);
            j = pi[j - 1];
        }
    }

    return ans;
}

Ең бастысы

КМП pattern-ді text ішінде іздейді
O(n + m) уақытта жұмыс істейді
prefix function қолданады
j қазіргі совпадение ұзындығын көрсетеді
қате болса → j = pi[j - 1]
occurrence табылса да откат жасаймыз