Suffix Automata

Συχνά σε διαγωνισμούς πληροφορικής (κυρίως στο ACM-ICPC αλλά από τώρα και στην IOI) εμφανίζονται προβλήματα τα οποία χρειάζονται ορισμένους αλγορίθμους σε αλφαριθμητικά για να λυθούν. Οι πιο περίπλοκοι όμως τέτοιοι αλγόριθμοι έχουν αρχίσει να εμφανίζονται τα τελευταία χρόνια, αν και υπήρχαν από πιο παλιά και χρησιμοποιούνταν κυρίως στα Linux. Μία από τις δυσκολότερες και ταυτόχρονα δυνατότερες δομές για αλφαριθμητικά είναι τα Suffix Automata. Τα Suffix Automata παρουσιάζουν μεγάλο ενδιαφέρον επειδή συνδυάζουν πολλές τεχνικές ταυτόχρονα εκτός από αλγορίθμους αλφαριθμητικών (θεωρία γράφων, δυναμικός προγραμματισμός).

• Ορισμός
• Παραδείγματα
• Σύνολο $endpos$ τερματικών θέσεων
• Επιθεματικοί σύνδεσμοι
• Συνοψίζοντας
• Κατασκευή
• Εφαρμογές
  • Υπάρχει ένα δοσμένο αλφαριθμητικό $w$ μέσα σε ένα άλλο $s$;
  • Είναι το $w$ επίθεμα του $s$;
  • Ποιο είναι το πλήθος των διαφορετικών υπο-αλφαριθμητικών του $s$;
  • Πόσες φορές εμφανίζεται το $w$ στο $s$;
  • Που εμφανίζεται για πρώτη φορά το $w$ μέσα στο $s$;
  • Σε ποιες θέσεις του $s$ εμφανίζεται το $w$;
• Προβλήματα
• Πηγές

Ορισμός

To Suffix Automaton ενός αλφαριθμητικού $S$ καλείται ο κατευθυνόμενος μη κυκλικός γράφος, στον οποίο οι κορυφές καλούνται καταστάσεις και οι ακμές μεταξύ αυτών μεταβάσεις μεταξύ των καταστάσεων.

• Μία από τις καταστάσεις $t_0$ καλείται η αρχική κατάσταση και πρέπει να είναι η πηγή (δηλαδή η κατάσταση που έχει πρόσβαση σε όλες τις άλλες).

• Κάθε μετάβαση στη μηχανή είναι μια ακμή με ένα σύμβολο του αλφαβήτου μας για ένδειξη. Όλες οι μεταβάσεις που ξεκινούν από μια κατάσταση πρέπει να έχουν διαφορετικές ενδείξεις.

• Μία ή περισσότερες καταστάσεις σημαδεύονται ως οι τερματικές καταστάσεις. Αν ξεκινήσουμε από την αρχική κατάσταση $t_0$, ακολουθήσουμε ένα οποιοδήποτε μονοπάτι προς κάποια τερματική κατάσταση και καθ’ όλη τη διάρκεια της διαδρομής γράφουμε τις ενδείξεις των ακμών που διασχίζουμε τότε θα πάρουμε ένα αλφαριθμητικό το οποίο πρέπει να αποτελεί επίθεμα του $S$.

• Το Suffix Automaton περιλαμβάνει τον μικρότερο αριθμό κορυφών από όλους τους πιθανούς γράφους που μπορεί να δημιουργηθούν με βάση τις παραπάνω ιδιότητες.

Παραδείγματα

Ας δούμε μερικά Suffix Automata. Η αρχική κατάσταση θα συμβολίζεται με $t_0$ και οι τερματικές με $*$.

1. Για το αλφαριθμητικό $s = ``"$:

2. Για το αλφαριθμητικό $s = ``a"$:

3. Για το αλφαριθμητικό $s = ``aa"$:

4. Για το αλφαριθμητικό $s = ``ab"$:

5. Για το αλφαριθμητικό $s = ``aba"$:

6. Για το αλφαριθμητικό $s = ``abb"$:

7. Για το αλφαριθμητικό $s = ``abbb"$:

Σύνολο $endpos$ τερματικών θέσεων

Ας θεωρήσουμε το μη μηδενικό υπό-αλφαριθμητικό $t$ του $S$. Ονομάζουμε $endpos(t)$ το σύνολο όλων των θέσεων στο $S$ στις οποίες τελειώνει μια εμφάνιση του $t$. Δύο αλφαριθμητικά ορίζονται ως ισοδύναμα αν τα σύνολα των τερματικών τους θέσεων $endpos$ είναι ίσα. Έτσι όλα τα μη μηδενικά υπο-αλφαριθμητικά $t$ μπορούν να χωριστούν σε ισοδύναμες κλάσεις σύμφωνα με τα σύνολα $endpos$.

Π.χ. μερικά $endpos$ σύνολα του $``ababc"$ είναι (αν οι θέσεις ξεκινούν από το 0) :

Παρατηρήστε πως $endpos(``b") = endpos(``ab")$. Αυτό σημαίνει ότι τα δύο αυτά αλφαριθμητικά ανήκουν στην ίδια ισοδύναμη κλάση.

Προκύπτει ότι σε ένα Suffix Automaton όλα τα αλφαριθμητικά μιας ισοδύναμης κλάσης αντιστοιχούν στην ίδια κατάσταση. Με άλλα λόγια, ο αριθμός των καταστάσεων σε ένα Suffix Automaton ισούται με τον αριθμό των ισοδύναμων κλάσεων συν ένα (από την αρχική κατάσταση). Αποδεικνύεται όμως ότι στην χειρότερη περίπτωση θα υπάρχουν το πολύ $2*len(S)$ διαφορετικές καταστάσεις!!! Αυτή την πρόταση θα την θεωρήσουμε δεδομένη. Ακολουθούν κάποιες απλές αλλά χρήσιμες προτάσεις σχετικά με τα σύνολα $endpos$.

Λήμμα 1: Δύο μη μηδενικά υπο-αλφαριθμητικά $u$ και $w$ με $length(u) <= length(w)$ είναι ισοδύναμα αν και μόνο αν οπουδήποτε υπάρχει το $u$ στο $S$ αποτελεί επίθεμα του $w$.

Η απόδειξη είναι σχεδόν προφανής: Για την απλή συνεπαγωγή, ισχύει ότι αφού το $u$ και το $w$ τελειώνουν στις ίδιες θέσεις στο $S$ τότε αναγκαστικά το ένα (μικρότερο) θα είναι επίθεμα του άλλου. Αντίστροφα, αν το $u$ εμφανίζεται στο $S$ μόνο σαν επίθεμα του $w$ τότε από τον ορισμό ξέρουμε ότι το $u$ τελειώνει στις ακριβώς ίδιες θέσεις με το $w$.

Λήμμα 2: Ας θεωρήσουμε ξανά δύο μη μηδενικά υπο-αλφαριθμητικά $u$ και $w$ με $length(u) <= length(w)$. Τότε τα σύνολά τους $endpos$ είναι είτε ξένα μεταξύ τους είτε το $endpos(w)$ περιέχεται πλήρως στο $endpos(u)$, το οποίο εξαρτάται από το αν το $u$ είναι επίθεμα του $w$ ή όχι.

Για παράδειγμα το $endpos(``aba")$ περιέχεται πλήρως στο $endpos(``a")$ αφού το $``a"$ είναι επίθεμα του $``aba"$.

Απόδειξη: Ας υποθέσουμε ότι τα σύνολα $endpos(u)$ και $endpos(w)$ έχουν τουλάχιστον ένα κοινό στοιχείο. Τότε αυτό σημαίνει ότι τα αλφαριθμητικά τελειώνουν στην ίδια θέση, δηλαδή το $u$ είναι επίθεμα του $w$. Αλλά τότε σε κάθε του εμφάνιση, το $w$ περιέχει στο τέλος του το $u$, κάτι που σημαίνει ότι το $endpos(w)$ περιέχεται πλήρως στο $endpos(u)$.

Λήμμα 3: Αν ταξινομήσουμε όλα τα υπο-αλφαριθμητικά σε μια ισοδύναμη κλάση κατά φθίνουσα σειρά μηκών, τότε στην τελική ακολουθία κάθε υπο-αλφαριθμητικό θα είναι μικρότερο του προηγούμενου και ταυτόχρονα θα είναι επίθεμά του. Με άλλα λόγια, τα υπο-αλφαριθμητικά που περιέχονται σε μια ισοδύναμη κλάση είναι επιθέματα μεταξύ τους και έχουν όλα τα πιθανά μήκη σε ένα διάστημα $[x, y]$.

Για παράδειγμα, αν εφαρμόσουμε την παραπάνω διαδικασία στην κλάση $\{2\}$ του προηγούμενου παραδείγματος θα πάρουμε την ακολουθία $``aba", ``ba"$ με μήκη στο $[2, 3]$.

Απόδειξη: Έστω μια ισοδύναμη κλάση. Αν περιέχει μόνο ένα αλφαριθμητικό τότε το Λήμμα είναι προφανώς σωστό. Ας υποθέσουμε τώρα ότι ο αριθμός των αλφαριθμητικών είναι μεγαλύτερος. Σύμφωνα με το Λήμμα 1, δύο αλφαριθμητικά σε μια ισοδύναμη κλάση είναι πάντα τέτοια ώστε το ένα να είναι επίθεμα του άλλου. Έτσι, σε μια ισοδύναμη κλάση δεν μπορούν να υπάρχουν αλφαριθμητικά ίδιου μεγέθους. Ας υποθέσουμε λοιπόν ότι το $w$ είναι το αλφαριθμητικό με το μεγαλύτερο μήκος σε ένα σύνολο $endpos$ και το $u$ είναι αυτό με το μικρότερο μήκος. Σύμφωνα με το Λήμμα 1, το $u$ είναι επίθεμα του $w$. Τώρα ας θεωρήσουμε ένα οποιοδήποτε επίθεμα του $w$ με μήκος στο διάστημα $[length(u), length(w)]$. Θα δείξουμε ότι ανήκει στην ίδια ισοδύναμη κλάση με το $w$. Στην πραγματικότητα το αλφαριθμητικό αυτό μπορεί να υπάρξει στο $S$ μόνο ως επίθεμα του $w$ αφού το μικρότερο επίθεμά του που υπάρχει μόνο ως επίθεμά του είναι το $u$. Έτσι, ξανά σύμφωνα με το Λήμμα 1, αυτό το αλφαριθμητικό ανήκει στην ίδια ισοδύναμη τάξη με τα άλλα δύο.

Επιθεματικοί σύνδεσμοι

Ας θεωρήσουμε μία κατάσταση $v$ στο Suffix Automaton διαφορετική της $t_0$. Όπως τώρα γνωρίζουμε, η $v$ αντιστοιχεί σε μία συγκεκριμένη ισοδύναμη κλάση αλφαριθμητικών που χαρακτηρίζεται από το $endpos$ σύνολό της, έτσι αν συμβολίσουμε με $w$ το αλφαριθμητικό με το μεγαλύτερο μήκος εκεί, τότε όλα τα υπόλοιπα θα είναι επιθέματα του $w$. Ξέρουμε επίσης ότι τα πρώτα μερικά μεγαλύτερα επιθέματα του $w$ ανήκουν επίσης στην ίδια ισοδύναμη κλάση ενώ όλα τα υπόλοιπα (τουλάχιστον το κενό) σε διαφορετικές. Ας συμβολίσουμε με $c$ την κλάση του μεγαλύτερου επιθέματος του $w$ που δεν ανήκει στην ίδια ισοδύναμη κλάση με αυτό. Προς αυτή θα βάλουμε έναν επιθεματικό σύνδεσμο (ή αλλιώς Suffix Link) και θα τον γράφουμε $link(v)$.

Θα υποθέτουμε στη συνέχεια ότι η αρχική κατάσταση $t0$ αντιστοιχεί σε μία ισοδύναμη κλάση, η οποία περιέχει μόνο ένα κενό αλφαριθμητικό και ισχύει $endpos(t_0) = [-1...length(S)-1]$.

Παρακάτω υπάρχει ένα παράδειγμα του Suffix Automaton (αριστερά) και των Suffix Links του (δεξιά) από το αλφαριθμητικό $``abcbc"$.

Παρατηρήστε πως τα $``abcb", ``bcb", ``cb"$ ανήκουν στην ίδια κλάση και ότι το μεγαλύτερο επίθεμα του $``abcb"$ που δεν ανήκει στην κλάση αυτή είναι το $``b"$ στο οποίο καταλήγει και το αντίστοιχο suffix link.

Λήμμα 4: Οι επιθεματικοί σύνδεσμοι (όπως φαίνεται και στο προηγούμενο παράδειγμα) σχηματίζουν ένα δέντρο, η ρίζα του οποίου είναι η αρχική κατάσταση $t_0$.

Απόδειξη: Θεωρούμε μια αυθαίρετη κατάσταση $v != t_0$. Ακολουθώντας τα suffix links από αυτή τη κατάσταση θα καταλήξουμε κάποτε στο $t_0$ που αντιστοιχεί στο κενό αλφαριθμητικό, αφού οι επιθεματικοί σύνδεσμοι καταλήγουν πάντα σε αλφαριθμητικά με γνησίως μικρότερο μήκος (αυτό προκύπτει από τον ορισμό των επιθεματικών συνδέσμων και το Λήμμα 3).

Λήμμα 5: Αν κατασκευάσουμε το δέντρο των $endpos$ έτσι ώστε κάθε κόμβος να είναι υποσύνολο κάθε προγόνου του, τότε θα έχουμε το ίδιο δέντρο που παίρνουμε από τα suffix links.

Απόδειξη: Είναι γεγονός ότι τα σύνολα $endpos$ μπορούν να κατασκευάσουν ένα δέντρο, γιατί όπως γνωρίζουμε από το Λήμμα 2, κάθε δύο σύνολα $endpos$ είναι είτε ξένα μεταξύ τους είτε το ένα περιέχεται στο άλλο. Τώρα ας θεωρήσουμε μια οποιαδήποτε κατάσταση $v != t_0$ και τον επιθεματικό της σύνδεσμο $link(v)$. Από τον ορισμό των επιθεματικών συνδέσμων και το Λήμμα 2 προκύπτει ότι $endpos(v) \subset endpos(link(v))$, το οποίο μαζί και με το Λήμμα 4 αποδεικνύουν τον ισχυρισμό μας.

Συνοψίζοντας

Προτού προχωρήσουμε στην περιγραφή του αλγορίθμου κατασκευής, θα συνοψίσουμε τα παραπάνω και θα εισάγουμε ορισμένους νέους συμβολισμούς.

• Όλα τα υπο-αλφαριθμητικά ενός αλφαριθμητικού $S$ μπορούν να διαιρεθούν σε κάποιες κλάσεις ισοδυναμίας σύμφωνα με το σύνολο $endpos$ των τερματικών τους θέσεων μέσα στο $S$.

• Ένα Suffix Automaton αποτελείται από την αρχική κατάσταση $t_0$ καθώς και από ένα κόμβο για κάθε ισοδύναμη κλάση. Συνολικά θα υπάρχουν το πολύ $2*len(S)$ καταστάσεις!!!

• Κάθε κατάσταση $v$ αντιστοιχεί σε ένα ή περισσότερα αλφαριθμητικά. Ας συμβολίσουμε με $longest(v)$ το αλφαριθμητικό της $v$ με το μεγαλύτερο μήκος και με $shortest(v)$ αυτό με το μικρότερο μήκος και $len(v)$, $minlen(v)$ τα μήκη τους αντίστοιχα. Τότε όλα τα αλφαριθμητικά που αντιστοιχούν σε αυτή την κατάσταση έχουν μήκος στο διάστημα $[minlen(v), len(v)]$.

• Για κάθε κατάσταση $v!=t_0$ ορίζεται ένας επιθεματικός σύνδεσμος που οδηγεί στην κατάσταση που αντιστοιχεί στο επίθεμα του $longest(v)$ με μήκος $minlen(v)-1$. Οι επιθεματικοί σύνδεσμοι σχηματίζουν ένα δέντρο με ρίζα το $t_0$ στο οποίο το $endpos$ του κάθε κόμβου είναι η ένωση όλων των παιδιών του.

• Έτσι το $minlen(v)$ μπορεί να βρεθεί ως εξής: $minlen(v) = len(link(v)) + 1$.

• Αν ξεκινήσουμε από μία αυθαίρετη κατάσταση $v_0$ και ακολουθήσουμε τους επιθεματικούς συνδέσμους θα καταλήξουμε αργά ή γρήγορα στην αρχική κατάσταση $t_0$. Επιπλέον καθώς ακολουθούμε τους συνδέσμους παίρνουμε μη επικαλυπτόμενα διαστήματα $[minlen(v_i), len(v_i)]$ των οποίων η ένωση αποτελεί ένα ενιαίο διάστημα.

Κατασκευή

Στη συνέχεια παρουσιάζουμε έναν online αλγόριθμο κατασκευής του Suffix Automaton ενός αλφαριθμητικού, που σημαίνει ότι θα το μεταβάλλουμε με κάθε νέο χαρακτήρα. Συνολικά ο αλγόριθμος είναι γραμμικός. Για να καταφέρουμε να καταναλώνουμε γραμμική μνήμη θα αποθηκεύουμε σε κάθε κατάσταση μόνο τις τιμές των len, link και τη λίστα των μεταβάσεων από αυτή την κατάσταση.

struct state {
    int len, link;
    map<char, int> delta;
    // Το map προσθέτει έναν επιπλέον log(k) παράγοντα,
    // αλλά θα μπορούσε να αντικατασταθεί με ένα hash table.
} st[2 * MAX_N]; // θυμηθείτε πως υπάρχουν το πολύ 2 * Ν καταστάσεις

Αρχικά, το Automaton αποτελείται μόνο από την αρχική κατάσταση, την οποία θα θεωρούμε την κατάσταση 0 (ενώ τις υπόλοιπες 1,2,3,…). Το len της θα ισούται με 0 και το link της, για άνεση, με -1 (μία φανταστική κατάσταση). Οπότε πριν από οτιδήποτε άλλο θα πρέπει να καλέσουμε την συνάρτηση init_sa() για να αρχικοποιήσει αυτές τις μεταβλητές.

int last, sz;

void init_sa() {
    last = 0;
    sz = 1;
    
    st[last].len = 0;
    st[last].link = -1;
    st[last].delta.clear();
}

Τώρα αυτό που μένει είναι να καταλάβουμε πώς αλλάζει η δομή όταν προσθέσουμε έναν νέο χαρακτήρα c στο τέλος του αλφαριθμητικού. Ακολουθεί η διαδικασία:

• Υποθέτουμε ότι η last είναι η τελευταία κατάσταση που προσθέσαμε, η οποία αντιστοιχεί σε ολόκληρο το αλφαριθμητικό. (Αρχικά η last ισούται με 0)

• Δημιουργούμε μία νέα κατάσταση cur και θέτουμε το len(cur) να είναι ίσο με len(last)+1. Προς το παρόν το link(cur) είναι αόριστο.

int cur = sz++;
st[cur].len = st[last].len + 1;
st[cur].delta.clear();

• Ακολουθούμε την εξής διαδικασία: Αρχικά είμαστε στο last. Όσο δεν υπάρχει μετάβαση από την τρέχουσα κατάσταση με τον χαρακτήρα c τότε την προσθέτουμε προς το cur (αυτό σημαίνει ότι όλα τα επιθέματα του S στην τρέχουσα κλάση μπορούν να μετασχηματιστούν με την προσθήκη του c σε επιθέματα του S+c και να ανήκουν στην κλάση cur) και ακολουθούμε τους επιθεματικούς συνδέσμους μέχρι να φτάσουμε σε μια κατάσταση που ήδη έχει μετάβαση με τον c ή στην -1.

for (p = last; p != -1 && !st[p].delta.count(c); p = st[p].link)
        st[p].delta[c] = cur;

• Αν με την προηγούμενη διαδικασία καταλήξαμε στην φανταστική κατάσταση -1, που σημαίνει ότι δεν φεύγει μετάβαση με τον χαρακτήρα c από καμία κατάσταση στη διαδρομή μας, τότε θέτουμε link(cur) = 0 και σταματάμε τον αλγόριθμο προσθήκης νέου χαρακτήρα.

• Ας υποθέσουμε τώρα ότι σταματήσαμε σε μια κατάσταση p, από την οποία υπάρχει μετάβαση με τον c. Ας συμβολίσουμε με q την κατάσταση στην οποία οδηγεί αυτή η μετάβαση.

• Τώρα υπάρχουν δύο περιπτώσεις σύμφωνα με το αν len(p) + 1 = len(q) ή όχι.

• Αν ισχύει τότε μπορούμε απλά να θέσουμε link(cur) = q και να σταματήσουμε (Σκεφτείτε γιατί ισχύει αυτό πριν προχωρήσετε!).

• Διαφορετικά (αν len(p) + 1 < len(q)) προκειμένου να “εξομοιώσουμε” την προηγούμενη περίπτωση κατασκευάζουμε μία κατάσταση κλώνο του q, ας την πούμε “clone”. Για να την δημιουργήσουμε αντιγράφουμε όλες τις μεταβάσεις από την q καθώς και τον επιθεματικό σύνδεσμο. Θέτουμε όμως len(clone) = len(p) + 1. Μετά την κλωνοποίηση θέτουμε το link(cur) αλλά και το link(q) να είναι ίσα με το clone. Τέλος, ακολουθώντας τους επιθεματικούς συνδέσμους από το p ελέγχουμε αν υπάρχει μετάβαση από την τρέχουσα κατάσταση στο q, αν ναι τότε την συνδέουμε στο clone και αν όχι σταματάμε.

void sa_extend(char c) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    st[cur].delta.clear();
    int p;
    for (p = last; p != -1 && !st[p].delta.count(c); p = st[p].link)
        st[p].delta[c] = cur;
    if (p == -1)
        st[cur].link = 0;
    else {
        int q = st[p].delta[c];
        if (st[p].len + 1 == st[q].len)
            st[cur].link = q;
        else {
            int clone = sz++;
            st[clone].delta = st[q].delta;
            st[clone].link = st[q].link;
            st[clone].len = st[p].len + 1;
            for (; p != -1 && st[p].delta[c] == q; p = st[p].link)
                st[p].delta[c] = clone;
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}

Συνιστούμε να εξομοιώσετε στο χαρτί τον αλγόριθμο με κάποια από τα αλφαριθμητικά των παραδειγμάτων και να ελέγξετε αν το Suffix Automaton βγήκε ίδιο με των εικόνων έτσι ώστε να σιγουρευτείτε ότι είναι ξεκάθαρη η διαδικασία!

Αν θέλουμε να σημαδέψουμε με κάποιον τρόπο τις τερματικές καταστάσεις, τότε ξεκινώντας από την τελευταία κατάσταση που προσθέσαμε και ακολουθώντας όλους τους επιθεματικούς συνδέσμους σημαδεύουμε όλες τις καταστάσεις που συναντήσαμε ως τερματικές (συμπεριλαμβανομένης της τελικής). Είναι προφανές ότι έτσι έχουμε καλύψει όλα τα επιθέματα του αλφαριθμητικού μας.

for (int p = last; p != 0; p = st[p].link)
    terminal[p] = true;

Εφαρμογές

Αυτό είναι ίσως το πιο ενδιαφέρον κομμάτι των Suffix Automata αφού μας επιτρέπουν να μετατρέψουμε προβλήματα αλφαριθμητικών σε προβλήματα γράφων. Μάλιστα το γεγονός ότι αποτελούν DAGs μας δίνει συχνά τη δυνατότητα να εφαρμόσουμε αλγορίθμους δυναμικού προγραμματισμού πάνω σε αυτά!

Συνιστούμε να προσπαθήσετε να λύσετε τα επόμενα προβλήματα από μόνοι σας πριν δείτε τις λύσεις.

Υπάρχει ένα δοσμένο αλφαριθμητικό $w$ μέσα σε ένα άλλο $s$;

Λύση: Αυτό το πρόβλημα είναι πολύ απλό αφού το μόνο που έχουμε να κάνουμε είναι να διατρέξουμε το Suffix Automaton του $s$ από την αρχική κατάσταση και να ελέγξουμε αν μπορούμε μέσα από διαδοχικές μεταβάσεις να σχηματίσουμε το $w$.

bool is_substring(const string &w) {
    int node = 0;
    for (int i = 0; i < (int)w.size(); i++) {
        if (!st[node].delta.count(w[i]))
            return false;
        node = st[node].delta[w[i]];
    }
    return true;
}

Είναι το $w$ επίθεμα του $s$;

Λύση: Αυτό είναι ένα εξίσου απλό πρόβλημα με το προηγούμενο, με την μόνη διαφορά ότι πρέπει να ελέγξουμε αν η τελευταία μας κατάσταση είναι τερματική ή όχι.

Ποιο είναι το πλήθος των διαφορετικών υπο-αλφαριθμητικών του $s$;

Λύση: Ο αριθμός αυτός ισούται με το πλήθος των διαφορετικών μονοπατιών στον γράφο μας ξεκινώντας από την αρχική κατάσταση. Αυτό είναι ένα πρόβλημα που μπορεί να λυθεί με τη χρήση δυναμικού προγραμματισμού. Η απάντηση για τον κόμβο $u$ ισούται με το άθροισμα όλων των $dp[v]$ τέτοια ώστε να υπάρχει ακμή από το $u$ στο $v$ συν 1 (για το μονοπάτι που σταματάει στο $u$).

void dfs(int u) {
    if (visit[u]) return;
    visit[u] = true;
    
    dp[u] = 1;
    for (auto v : st[u].delta) {
        dfs(v.second);
        dp[u] += dp[v.second];
    }
}

Πόσες φορές εμφανίζεται το $w$ στο $s$;

Λύση: Οποιοδήποτε υπο-αλφαριθμητικό αποτελεί πρόθεμα ενός επιθέματος του $s$! Έτσι μπορούμε να προχωρήσουμε στους κόμβους του Suffix Automaton του $s$ μέχρι να φτάσουμε σε αυτόν που αντιστοιχεί στο $w$, ας πούμε στον $p$. Στη συνέχεια (με όμοιο τρόπο με το τελευταίο πρόβλημα) μας ενδιαφέρει να ξέρουμε πόσα επιθέματα του $s$ μπορούμε να καλύψουμε αν συνεχίσουμε την διαδρομή μας (δηλαδή πόσων επιθεμάτων αποτελεί το $w$ πρόθεμα). Για αυτόν τον λόγο αρκεί να επιστρέψουμε το πλήθος των μονοπατιών που ξεκινούν από το $p$ και τελειώνουν σε μία τερματική κατάσταση.

Που εμφανίζεται για πρώτη φορά το $w$ μέσα στο $s$;

Λύση: Το πρόβλημα είναι ισοδύναμο με το να υπολογίσουμε το μακρύτερο μονοπάτι που ξεκινάει από το $p$ (όπως ορίστηκε στη προηγούμενη λύση) και τελειώνει σε κάποια τερματική κατάσταση. Έτσι έχουμε βρει ποια είναι η μέγιστη δυνατή απόσταση από το τέλος του προθέματος (ίσου με $w$) ενός επιθέματος του $s$ προς το τέλος του $s$.

Σε ποιες θέσεις του $s$ εμφανίζεται το $w$;

Πρώτη Λύση: Όπως και στα προηγούμενα προβλήματα μπορούμε να διατρέξουμε το Automaton του $s$ μέχρι να φτάσουμε στο $p$. Στη συνέχεια αρκεί να κάνουμε μία DFS από εκεί και να υπολογίσουμε όλες τις αποστάσεις του $p$ από κάποια τερματική κατάσταση (δηλαδή τις αποστάσεις μιας εμφάνισης του $w$ από το τέλος του $s$).

Αξίζει όμως να αναφέρουμε άλλη μία ενδιαφέρουσα λύση η οποία χρησιμοποιεί τα suffix links.

Δεύτερη Λύση: Αρχικά κατασκευάζουμε το δέντρο που σχηματίζεται από τα suffix links.

tree = vector<vector<int> >(sz);

for (int i = 0; i < sz; i++)
    if (st[i].link >= 0)
        tree[st[i].link].push_back(i);

Ύστερα εφαρμόζουμε την ίδια διαδικασία με πριν και φτάνουμε στον κόμβο $p$. Από αυτόν αρκεί να τρέξουμε μια DFS στο δέντρο μέχρι να φτάσουμε στα φύλλα. Το $w$ θα εμφανίζεται τόσες φορές όσες είναι τα φύλλα που συναντήσαμε και χρησιμοποιώντας το len των φύλλων αυτών μπορούμε να προσδιορίσουμε και τις θέσεις στις οποίες τελειώνει μια εμφάνισή του.

Προβλήματα

Spoj SUBST1

Spoj ADACLEAN

Spoj SUBLEX

Πηγές

e-maxx Suffix Automata (μέσω google translate)

codeforces A Short Guide to Suffix Automata

Σχόλια