uniolympiads English

Συνάρτηση προθέματος (KMP)

Για κάθε θέση, το μακρύτερο γνήσιο πρόθεμα που είναι και επίθεμα. Δίνει αναζήτηση μοτίβου σε O(n+m)O(n + m) και τις «περιόδους» μιας λέξης.

Πότε

Βρες όλες τις εμφανίσεις ενός μοτίβου, ή απάντα σε ερωτήσεις για τη δομή μιας λέξης: σύνορα (borders), περίοδοι, πόσες φορές επαναλαμβάνεται ένα πρόθεμα.

Η ιδέα

πi\pi_i είναι το μήκος του μακρύτερου γνήσιου προθέματος του s0…sis_0 \dots s_i που είναι και επίθεμά του. Για s=abacabas = \texttt{abacaba}, π=(0,0,1,0,1,2,3)\pi = (0, 0, 1, 0, 1, 2, 3).

Το κλειδί: αν το s0…sk−1s_0 \dots s_{k-1} είναι επίθεμα που ταιριάζει και το si≠sks_i \ne s_k, το επόμενο μικρότερο υποψήφιο μήκος δεν είναι k−1k - 1 αλλά πk−1\pi_{k-1}. Οποιοδήποτε σύνορο του s0…si−1s_0 \dots s_{i-1} μικρότερο από kk είναι σύνορο και του s0…sk−1s_0 \dots s_{k-1}. Γι' αυτό ο εσωτερικός βρόχος κάνει k=πk−1k = \pi_{k-1}.

Το kk αυξάνεται το πολύ κατά 1 ανά βήμα και κάθε επανάληψη του εσωτερικού βρόχου το μειώνει. Άρα συνολικά O(n)O(n).

Αναζήτηση. Φτιάξε το p+#+tp + \texttt{\#} + t. Μια θέση με πi=∣p∣\pi_i = |p| σημαίνει εμφάνιση του pp που τελειώνει εκεί. Το #\texttt{\#} δεν πρέπει να υπάρχει σε καμία από τις δύο λέξεις, ώστε κανένα ταίριασμα να μην το διασχίζει.

Σύνορα. Όλα τα σύνορα της λέξης είναι τα πn−1\pi_{n-1}, ππn−1−1\pi_{\pi_{n-1}-1}, … μέχρι το 0. Η μικρότερη περίοδος είναι n−πn−1n - \pi_{n-1}.

Παγίδες

  • Η συνάρτηση προθέματος και η Z-function λύνουν σχεδόν τα ίδια προβλήματα. Μάθε καλά τη μία, και αναγνώρισε την άλλη όταν τη δεις σε λύση.
  • Το findAll φτιάχνει ένα νέο string μήκους n+m+1n + m + 1. Σε όριο μνήμης αυτό σπάνια μετράει, αλλά αν μετράει, τρέξε το ταίριασμα πάνω στο tt κρατώντας μόνο το π\pi του pp.

Κώδικας

Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.

cpp/kmp.cpp
// Prefix function (Knuth–Morris–Pratt).
// pi[i] = length of the longest proper prefix of s[0..i] that is also a suffix of it. O(n).
// findAll: every position where pattern occurs in text, via the string pattern + '#' + text.
// The separator must not appear in either string.

vector<int> prefixFunction(const string& s) {
    int n = s.size();
    vector<int> pi(n, 0);
    for (int i = 1; i < n; i++) {
        int k = pi[i - 1];
        while (k > 0 && s[i] != s[k]) {
            k = pi[k - 1];
        }
        if (s[i] == s[k]) {
            k++;
        }
        pi[i] = k;
    }
    return pi;
}

vector<int> findAll(const string& text, const string& pattern) {
    vector<int> result;
    int m = pattern.size();
    if (m == 0) {
        return result;
    }
    vector<int> pi = prefixFunction(pattern + '#' + text);
    for (int i = 2 * m; i < (int)pi.size(); i++) {
        if (pi[i] == m) {
            result.push_back(i - 2 * m);
        }
    }
    return result;
}

Ελέγχθηκε σε 3.000 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Για εξάσκηση στο CSES

Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.

Περισσότερα στο USACO Guide

Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.