uniolympiads English

Z-function

Για κάθε θέση ii, πόσοι χαρακτήρες από το ii συμπίπτουν με την αρχή της λέξης. Σε O(n)O(n), με ένα «παράθυρο» που ξέρουμε ήδη.

Πότε

Ό,τι και η συνάρτηση προθέματος: αναζήτηση μοτίβου, περίοδοι, σύνορα. Μερικές φορές η Z είναι πιο φυσική, π.χ. όταν ρωτάς «πόσο μεγάλο κοινό πρόθεμα έχει κάθε επίθεμα με ολόκληρη τη λέξη».

Η ιδέα

ziz_i είναι το μήκος του μακρύτερου κοινού προθέματος του ss και του sisi+1…s_i s_{i+1} \dots Κατά σύμβαση z0=0z_0 = 0.

Κρατάμε το παράθυρο [l,r)[l, r) που τελειώνει πιο δεξιά ανάμεσα σε όσα έχουμε βρει, με sl…sr−1=s0…sr−l−1s_l \dots s_{r-1} = s_0 \dots s_{r-l-1}. Για i<ri < r, το sis_i βρίσκεται μέσα στο παράθυρο, άρα ό,τι ξέρουμε για τη θέση i−li - l ισχύει και εδώ, το πολύ μέχρι το rr:

zi≥min⁡(r−i, zi−l).z_i \ge \min(r - i,\ z_{i-l}).

Από εκεί συνεχίζουμε τη σύγκριση χαρακτήρα προς χαρακτήρα. Κάθε επιτυχής σύγκριση πέρα από το rr μετακινεί το rr δεξιά, άρα το σύνολο είναι O(n)O(n).

Αναζήτηση. zz του p+#+tp + \texttt{\#} + t: εμφάνιση του pp στη θέση jj του tt όπου z∣p∣+1+j=∣p∣z_{|p| + 1 + j} = |p|.

Παγίδες

  • Το z0z_0 είναι σύμβαση. Κάποια προβλήματα θέλουν z0=0z_0 = 0, άλλα z0=nz_0 = n. Διάβασε την εκφώνηση.

Κώδικας

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

cpp/z-function.cpp
// 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

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

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

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