Ciao a tutti di nuovo
Questa volta mi trovo bloccato sulla risoluzione di words
Con una semplice dp di complessita’ O(n l) posso ottenere il numero di sequenze dato uno o piu’ trigrammi di partenza di ogni lunghezza da 3 a l caratteri (o da 0 a l-2 trigrammi)
Il problema sta nel ricavare la soluzione perche’ so quante stringhe terminano in con un trigramma ma non quante ce l’hanno all’inizio
Per fare questo potrei chiamare quella stessa funzione n volte ciascuna con un trigramma di partenza diverso, ma andrei nell’ordine di O(n^2 l)
Il codice lo posto solo per dimostrare che ci ho gia’ pensato su a lungo ma chiedo soltanto un hint
grazie in anticipo
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
ll n, l, k;
vector<string> t;
vector<vi> adj;
vector<vi> memo;
int main() {
// trovo molto piu' sensato che k sia la k-esima parola in ordine
// mentre n il numero di trigrammi
cin >> k >> l >> n;
l -= 2;
// t e' il vettore contenente i trigrammi
t.resize(n);
// adj e' la lista di adiacenza
adj.resize(n);
// memo[i][j] contiene il numero di sequenze di lunghezza i trigrammi
// che terminano in t[j]
// siccome per il calcolo di ogni valore si utilizza la riga
// precedente allora si puo' tagliare a solo 2 righe
memo.resize(2, vi(n));
// assegnando 1 a tutta la riga il calcolo si applica a tutte le sequenze
// assegnando 1 solo a determinati j si calcolano solo le sequenze che iniziano in t[j]
memo[0].assign(n, 1);
for (int i = 0; i < n; i++) cin >> t[i];
// il sort permette di calcolare l'adiacenza in O(n log(n)) invece che O(n^2)
sort(t.begin(), t.end());
for (int i = 0; i < n; i++) {
string s = t[i];
// metodo brutale per ottenere le ultime 2 lettere del trigramma
string bi = ""; bi += s[1]; bi += s[2];
int low = lower_bound(t.begin(), t.end(), bi) - t.begin();
bi += 'z'+1;
int high = lower_bound(t.begin(), t.end(), bi) - t.begin();
for (int j = low; j != high; j++)
adj[i].push_back(j);
}
// b serve per decretare la riga corretta da leggere/scrivere
// e si alterna ad ogni iterazione
bool b = false;
for (int i = 0; i < l-1; i++) {
b = not b;
for (int j = 0; j < n; j++) {
for (auto u: adj[j]) {
memo[not b][u] += memo[b][j];
memo[not b][u];
}
}
}
}