Z-function
Για κάθε θέση , πόσοι χαρακτήρες από το συμπίπτουν με την αρχή της λέξης. Σε , με ένα «παράθυρο» που ξέρουμε ήδη.
Πότε
Ό,τι και η συνάρτηση προθέματος: αναζήτηση μοτίβου, περίοδοι, σύνορα. Μερικές φορές η Z είναι πιο φυσική, π.χ. όταν ρωτάς «πόσο μεγάλο κοινό πρόθεμα έχει κάθε επίθεμα με ολόκληρη τη λέξη».
Η ιδέα
είναι το μήκος του μακρύτερου κοινού προθέματος του και του Κατά σύμβαση .
Κρατάμε το παράθυρο που τελειώνει πιο δεξιά ανάμεσα σε όσα έχουμε βρει, με . Για , το βρίσκεται μέσα στο παράθυρο, άρα ό,τι ξέρουμε για τη θέση ισχύει και εδώ, το πολύ μέχρι το :
Από εκεί συνεχίζουμε τη σύγκριση χαρακτήρα προς χαρακτήρα. Κάθε επιτυχής σύγκριση πέρα από το μετακινεί το δεξιά, άρα το σύνολο είναι .
Αναζήτηση. του : εμφάνιση του στη θέση του όπου .
Παγίδες
- Το είναι σύμβαση. Κάποια προβλήματα θέλουν , άλλα . Διάβασε την εκφώνηση.
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// Z-function. z[i] = length of the longest common prefix of s and s[i..]; z[0] = 0 by convention.
// [l, r) is the rightmost window that matches a prefix; inside it z[i] starts from z[i - l]. O(n).
vector<int> zFunction(const string& s) {
int n = s.size();
vector<int> z(n, 0);
int l = 0;
int r = 0;
for (int i = 1; i < n; i++) {
if (i < r) {
z[i] = min(r - i, z[i - l]);
}
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
if (i + z[i] > r) {
l = i;
r = i + z[i];
}
}
return z;
}
Ελέγχθηκε σε 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
- String Functions · String Algorithms
Περισσότερα στο USACO Guide
- String Searching · usaco.guide/adv/string-search
Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.