22ος ΠΔΠ B' Φάση: Πρόβλημα στον «Έξυπνο» Διαδραστικό Πίνακα (matrix) - Λύση
Επεξήγηση εκφώνησης
Μας δίνονται δύο συμβολοσειρές \(A\) και \(B\) και μας ζητείται να βρούμε αν (και πού) εμφανίζεται η \(A\) μέσα στην \(B\).
Ξεκινάμε με την brute force λύση που θέλει \(\mathcal{O}(NM)\) χρόνο και είναι αρκετή για να περάσει όλα τα testcases του προβλήματος. Συνεχίζουμε μετά με τρεις λύσεις που λύνουν το πρόβλημα σε \(\mathcal{O}(N + M)\) χρόνο. Οι λύσεις αυτές μπορούν να διαβαστούν ανεξάρτητα μεταξύ τους, αν έχετε ήδη κάποιες γνώσεις για τις τεχνικές που χρησιμοποιούν.
Brute force λύση
Η brute force λύση είναι να δοκιμάσουμε να συγκρίνουμε κάθε δυνατή υποσυμβολοσειρά της \(B\) με την \(A\). Πιο συγκεκριμένα, για κάθε θέση \(i = 0, 1, \ldots \lvert B \rvert - N\) ελέγχουμε αν \(B_{i}B_{i+1} \ldots B_{i + N - 1} = A_0 A_1 \ldots A_{N-1}\). Ο έλεγχος γίνεται με ένα for loop, το οποίο μπορούμε να σταματήσουμε νωρίς (με break) αν βρούμε ένα στοιχείο που να διαφέρουν οι συμβολοσειρές.
Στην χειρότερη περίπτωση για κάθε \(i\) η σύγκριση θέλει \(\mathcal{O}(N)\) χρόνο και αφού υπάρχουν \(M - N + 1\) δυνατά \(i\), ο αλγόριθμος χρειάζεται συνολικά \(N \cdot (M - N + 1) = \mathcal{O}(NM)\) χρόνο.
Ο αλγόριθμος αυτός είναι αρκετά γρηγορος για να περάσει όλα τα testcases. Οι επόμενοι αλγόριθμοι λύνουν το πρόβλημα σε \(\mathcal{O}(N + M)\) χρόνο.
#include <cstdio>
const size_t MAXN = 1024;
const size_t MAXM = 65536;
char A[MAXN];
char B[MAXM];
int main() {
long N, M;
FILE *fi = fopen("matrix.in", "r");
fscanf(fi, "%ld\n", &N);
for (long i = 0; i < N; ++i) {
A[i] = fgetc(fi);
}
fscanf(fi, "%ld\n", &M);
for (long i = 0; i < M; ++i) {
B[i] = fgetc(fi);
}
long found_pos = -1;
for (long i = 0; i <= M - N; ++i) {
bool found_different = false;
for (long j = 0; j < N; ++j) {
if (B[i + j] != A[j]) {
found_different = true;
break;
}
}
if (!found_different) {
found_pos = i + 1;
break;
}
}
FILE *fo = fopen("matrix.out", "w");
if (found_pos == -1) fprintf(fo, "F\n");
else fprintf(fo, "%ld\n", found_pos);
return 0;
}
Σημείωση: Την ίδια πολυπλοκότητα έχει και ο αλγόριθμος strstr της C (ολόκληρος ο κώδικας εδώ) και το std::string::find της C++.
Λύση με Αλγόριθμο Z
Η λύση αυτή προαπαιτεί γνώσεις για τον αλγόριθμο Z. Μπορείτε να διαβάσετε περισσότερα εδώ ή εδώ.
Ο αλγόριθμος Z υπολογίζει για μία συμβολοσειρά \(S\), τον πίνακα \(Z\), όπου \(Z[i]\) είναι το μήκος της μακρύτερης ακολουθίας που ξεκινάει από το \(i\)-οστό στοιχείο και \(A_0 A_1 \ldots A_{Z[i]} = A_{i}A_{i+1} \ldots A_{i + Z[i] - 1}\). Για παράδειγμα για \(S = \text{αβαβαβααβγαβ}\), ο πίνακας είναι ο εξής:
Ο αλγόριθμος Z χρειάζεται \(\mathcal{O}(\lvert S\rvert)\) χρόνο. Τώρα, για να βρούμε αν η \(A\) εμφανίζεται στη \(B\), θέτουμε \(S = A + B\) και βρίσκουμε το μικρότερο \(i > 0\), ώστε \(Z[i] \geq N\). Όταν \(Z[i] \geq N\), σημαίνει ότι \(A = S_0S_1 \ldots S_{N - 1} = S_{i}S_{i+1} \ldots S_{i + Z[i] - 1}\), που είναι και το ζητούμενο. Άρα αυτό μας επιτρέπει να λύσουμε το πρόβλημα σε \(\mathcal{O}(N + M)\) χρόνο.
// Υπολογισμος του πίνακα Z για την S = Α + Β.
long len = N + M;
long L = 0, R = 0;
Z[0] = len;
for (long i = 1; i < len; ++i) {
Z[i] = 0;
if (i <= R) Z[i] = std::min(R - i + 1, Z[i - L]);
while (i + Z[i] < len && S[Z[i]] == S[i + Z[i]]) Z[i]++;
if (i + Z[i] - 1 > R) {
L = i; R = i + Z[i] - 1;
}
// Αν κάποιο στοιχείο έχει N στοιχεία ή περισσότερα κοινά
// με το prefix της συμβολοσειράς, τότε βρήκαμε μία
// εμφάνιση της Α.
if (Z[i] >= N) {
found_pos = i - N + 1;
break;
}
}
Ολόκληρος ο κώδικας βρίσκεται εδώ.
Λύση με KMP
Η λύση αυτή προαπαιτεί γνώσεις για τον αλγόριθμο KMP. Μπορείτε να διαβάσετε περισσότερα εδώ.
Έστω \(S\) μία συμβολοσειρά και για ευκολία ας υποθέσουμε ότι ξεκινάει από το \(1\). Ο αλγόριθμος KMP υπολογίζει τον πίνακα \(F\), όπου \(F[0] = -1\) και \(F[i]\) για \(i > 0\) είναι το μήκος της μακρύτερης υποακολουθίας που τελειώνει στο στοιχείο \(i\) και \(S_1 S_2 \ldots S_{F[i]} = S_{i - F[i] + 1} S_{i - F[i] + 2} \ldots S_{i}\). Για παράδειγμα για \(S = \text{αβαβαβααβγαβ}\), ο πίνακας είναι ο εξής:
Ξεκινώντας και τις δύο συμβολοσειρές από την θέση \(1\), ο κώδικας είναι ο εξής.
// Υπολογισμός της failure function.
F[0] = -1;
long k = -1;
for(long i = 1; i <= N; i++) {
while(k >= 0 && A[k+1] != A[i]) k = F[k];
F[i] = ++k;
}
Ο αλγόριθμος KMP χρειάζεται \(\mathcal{O}(\lvert S \rvert)\) χρόνο. Για την εύρεση του \(A\) στο \(B\), για κάθε θέση \(j\) του \(B\) βρίσκουμε το μακρύτερο prefix του \(A\), μήκους \(k\), που είναι suffix του \(B_1 \ldots B_j\). Αν \(k = N\), τότε βρήκαμε μία εμφάνιση του \(A\). Για να υπολογίσουμε το \(k\) ξεκινάμε από τα αριστερά προς τα δεξιά. Στην αρχή το \(k = 0\). Στην θέση \(i\):
- Αν \(B[i] = A[k+1]\), τότε αυξάνουμε το \(k\) και τερματίζουμε.
- Διαφορετικά, αν \(B[i] \neq A[k+1]\), τότε θέτουμε \(k = F[k]\), και επιστρέφουμε στο 1.
Όταν έχουμε \(B[i] \neq A[k+1]\), σημαίνει ότι δεν μπορούμε να επεκτείνουμε το \(A_1 A_2\ldots A_k = B_{i - k + 1} B_{i - k + 2} \ldots B_{i-1}\) κατά μία θέση. Επομένως, πρέπει να βρούμε ένα μικρότερο suffix του \(B[i]\) που είναι prefix του \(A\), χρησιμοποιώντας ότι \(A_1 A_2\ldots A_k = B_{i - k + 1} B_{i - k + 2} \ldots B_{i}\). Αυτή την τιμή ακριβώς την έχουμε υπολογίσει στο \(F[k]\), άρα θέτουμε \(k = F[k]\).
// Εύρεση συμβολοσειράς.
long found_pos = -1;
k = 0;
for(long i = 1; i <= M; i++) {
while(k >= 0 && A[k+1] != B[i]) k = F[k];
k++;
if(k == N) {
found_pos = i - N + 1;
break;
}
}
Ολόκληρος ο κώδικας βρίσκεται εδώ.
Λύση με Rolling Hash
Η λύση αυτή προαπαιτεί γνώσεις για το rolling hash. Μπορείτε να διαβάσετε περισσότερα εδώ.
Για μία ακολουθία \(S\) με μήκος \(N\), το rolling hash \(h(S)\) ορίζεται ως
\[h(S) = S_0 \cdot b^{N-1} + S_1 \cdot b^{N-2} + \ldots + S_{N-2} \cdot b + S_{N-1} \pmod{p}\]για κάποιον θετικό ακέραιο \(b\) και έναν πρώτο αριθμό \(p\). Η ιδέα είναι ότι όταν συγκρίνουμε συμβολοσειρές \(S_1\) και \(S_2\) αντί να κοιτάξουμε αν όλοι οι χαρακτήρες είναι ίσοι μεταξύ τους (με \(\lvert S_1 \rvert\) συγκρίσεις) κοιτάμε μόνο αν \(h(S_1) = h(S_2)\). Υπάρχει η πιθανότητα ο αλγόριθμος να κάνει λάθος, γιατί μπορεί δύο ακολουθίες να έχουν το ίδιο hash (αφού υπάρχουν μόνο \(p\) δυνατές τιμές και πολύ περισσότερες συμβολοσειρές). Για να μειώσουμε αυτή την πιθανότητα διαλέγουμε \(p\) έναν “μεγάλο” πρώτο αριθμό και \(B = 222\), το εύρος τον πιθανών τιμών. Για να είμαστε σίγουροι ότι ο αλγόριθμος θα δώσει τη σωστή απάντηση, όταν \(h(S_1) = h(S_2)\) ελέχουμε και αν όντως οι ακολουθίες είναι ίσες. Με τα δοσμένα testcases, δεν κάνει διαφορά άμα προσθέσουμε ή όχι αυτόν τον έλεγχο.
Παρατήρηση 1η: Αν στην ακολουθία \(S\) προσθέσουμε έναν χαρακτήρα \(x\) στο τέλος της, παίρνοντας την \(S'\), τότε \(h(S') = h(S) \cdot B + x\).
(Αιτιολόγηση) Γράφοντας τον ορισμό της \(h\) για την \(S'\),
\[\begin{align*} h(S') & = S_0' \cdot b^{N} + S_1' \cdot b^{N-1} + \ldots + S_{N-1}' \cdot b + S_{N}' \pmod{p} \\ & = S_0 \cdot b^{N-1} + S_1 \cdot b^{N-2} + \ldots + S_{N-1} \cdot b + x \pmod{p} \\ & = (S_0 \cdot b^{N-2} + S_1 \cdot b^{N-1} + \ldots + S_{N-1}) \cdot b + x \pmod{p} \\ & = h(S) \cdot b + x \pmod{p}. \end{align*}\]Παρατήρηση 2η: Αν από την ακολουθία \(S\) αφαιρέσουμε τον πρώτο χαρατήρα, παίρνοντας την \(S'\), τότε \(h(S') = h(S) - S_0 \cdot b^N \pmod{p}\).
Συνδυάζοντας αυτές τις δύο παρατηρήσεις, μας επιτρέπει να υπολογίσουμε όλα τα hash των συμβολοσειρών μεγέθους \(N\) της \(B\). Πιο συγκεκριμένα ξεκινάμε υπολογίζοντας το \(h(B_0 \ldots B_{N-1})\) και το \(\text{pow} = b^N \pmod{p}\). Τώρα γνωρίζοντας το \(h(B_i\ldots B_{i + N - 1})\), έχουμε ότι \(h(B_{i+1}\ldots B_{i + N}) = h(B_i\ldots B_{i + N - 1}) \cdot b + B_{i + N} - B_i \cdot \text{pow} \pmod{p}\). Αυτές οι πράξεις θέλουν \(\mathcal{O}(1)\) χρόνο, και κάθε σύγκριση θέλει \(\mathcal{O}(1)\) χρόνο, άρα αν δεν υπάρχει λάθος ο αλγόριθμος χρειάζεται \(\mathcal{O}(N)\) χρόνο.
#include <cstdio>
const size_t MAXN = 1024;
const size_t MAXM = 65536;
typedef long long ll;
char A[MAXN];
char B[MAXM];
ll range = 222;
ll base = (1 << 31) - 1;
// Μετατρέπει τους χαρακτήρες από το [-127,+127]
// στο [0, 221] (αφού η εκφώνηση μας δίνει ότι οι χαρακτήρες
// είναι μεταξύ [33, 254]
int norm_char(char c) {
return c + 256 - 33;
}
// Προσθέτει έναν χαρακτήρα στο hash.
ll add_hash(char c, ll hash) {
return (norm_char(c) + hash * range) % base;
}
int main() {
long N, M;
FILE *fi = fopen("matrix.in", "r");
fscanf(fi, "%ld\n", &N);
long long hash_A = 0;
for (long i = 0; i < N; ++i) {
A[i] = fgetc(fi);
hash_A = add_hash(A[i], hash_A);
}
fscanf(fi, "%ld\n", &M);
for (long i = 0; i < M; ++i) {
B[i] = fgetc(fi);
}
long found_pos = -1;
// Υπολογίζουμε το rolling hash των πρώτων N στοιχείων
// και την N-οστή δυναμη της range.
long long pow = 1, hash_B = 0;
for (long i = 0; i < N; ++i) {
pow = (pow * range) % base;
hash_B = add_hash(B[i], hash_B);
}
// Δοκιμάζουμε κάθε δυνατή υπο-συμβολοσειρά μήκους N, αν έχει
// το ίδιο hash με την A.
for (long i = N; i <= M; ++i) {
if (hash_B == hash_A) {
// Ελέγχουμε ότι όντως
// Στα δοσμένα testcases, ακόμα και αν αφαιρέσουμε τον
// έλεγχο ο κώδικας τα περνάει επιτυχώς.
bool found_diff = false;
for (long j = 0; j < N; ++j) {
if (A[j] != B[i - N + j]) {
found_diff = true;
break;
}
}
if (!found_diff) found_pos = i + 1 - N;
break;
}
if (i < M) {
hash_B = add_hash(B[i], hash_B);
// Αφαιρούμε τον i - N χαρακτήρα ώστε το
// hash_B να κρατάει το hash B[i-N+1, i].
hash_B = (base + (hash_B - pow * norm_char(B[i - N])) % base) % base;
}
}
FILE *fo = fopen("matrix.out", "w");
if (found_pos == -1) fprintf(fo, "F\n");
else fprintf(fo, "%ld\n", found_pos);
return 0;
}
Σημείωση: Με τον έλεγχο στην χειρότερη περίπτωση ο αλγόριθμος χρειάζεται \(\mathcal{O}(N^2)\) χρόνο.