Συνάρτηση προθέματος (KMP)
Για κάθε θέση, το μακρύτερο γνήσιο πρόθεμα που είναι και επίθεμα. Δίνει αναζήτηση μοτίβου σε και τις «περιόδους» μιας λέξης.
Πότε
Βρες όλες τις εμφανίσεις ενός μοτίβου, ή απάντα σε ερωτήσεις για τη δομή μιας λέξης: σύνορα (borders), περίοδοι, πόσες φορές επαναλαμβάνεται ένα πρόθεμα.
Η ιδέα
είναι το μήκος του μακρύτερου γνήσιου προθέματος του που είναι και επίθεμά του. Για , .
Το κλειδί: αν το είναι επίθεμα που ταιριάζει και το , το επόμενο μικρότερο υποψήφιο μήκος δεν είναι αλλά . Οποιοδήποτε σύνορο του μικρότερο από είναι σύνορο και του . Γι' αυτό ο εσωτερικός βρόχος κάνει .
Το αυξάνεται το πολύ κατά 1 ανά βήμα και κάθε επανάληψη του εσωτερικού βρόχου το μειώνει. Άρα συνολικά .
Αναζήτηση. Φτιάξε το . Μια θέση με σημαίνει εμφάνιση του που τελειώνει εκεί. Το δεν πρέπει να υπάρχει σε καμία από τις δύο λέξεις, ώστε κανένα ταίριασμα να μην το διασχίζει.
Σύνορα. Όλα τα σύνορα της λέξης είναι τα , , … μέχρι το 0. Η μικρότερη περίοδος είναι .
Παγίδες
- Η συνάρτηση προθέματος και η Z-function λύνουν σχεδόν τα ίδια προβλήματα. Μάθε καλά τη μία, και αναγνώρισε την άλλη όταν τη δεις σε λύση.
- Το
findAllφτιάχνει ένα νέο string μήκους . Σε όριο μνήμης αυτό σπάνια μετράει, αλλά αν μετράει, τρέξε το ταίριασμα πάνω στο κρατώντας μόνο το του .
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// 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
Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.
- String Matching · String Algorithms
- Finding Borders · String Algorithms
- String Functions · String Algorithms
Περισσότερα στο USACO Guide
- String Searching · usaco.guide/adv/string-search
Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.