W zadaniu mamy daną gramatykę bezkontekstową oraz zbiór słów zabronionych. Dla każdego nieterminala gramatyki chcemy znaleźć długość najkrótszego słowa generowanego z tego nieterminala, które nie zawiera żadnego zabronionego słowa.
Należy zwrócić uwagę, że czasem reguły mogą się nie zakończyć (jeśli jest cykl). Takie rzeczy ignorujemy.
Wprowadźmy też oznaczenie: $N$ to będzie sumaryczna długość reguł gramatyki, a $M$ to sumaryczna długość słów zabronionych. Z ograniczeń w zadaniu mamy $N \leq 100$ oraz $M \leq 50$.
W podzadaniu 1 nie mamy żadnych słów zabronionych. W tym przypadku musimy po prostu obliczyć najkrótsze słowo generowane z nieterminala. Do tego przyda nam się adaptacja algorytmu Dijkstry.
Każdy symbol gramatyki $g$ (czyli terminal 0 i 1 lub nieterminal) będzie w jednym z trzech stanów: niegotowy (nie znamy długości najkrótszego słowa generowanego z tego symbolu), gotowy (mamy już obliczoną długość słowa $dist[g]$ i możemy jej użyć do obliczeń na regułach, które mają ten symbol po prawej stronie), oraz przetworzony (wykonaliśmy już obliczenia dla wystąpień tego symbolu po prawej stronie).
Dla każdej reguły $r$ będziemy utrzymywać liczbę nieprzetworzonych symboli z prawej strony $mut\_left[r]$ oraz aktualną długość słowa $len[r]$ wynikającą z przetworzonych symboli.
Symbole gotowe będą wrzucane na kolejkę priorytetową, posortowaną po długości ich słów. Przetwarzanie symbolu będzie odpowiadać relaksacji krawędzi w algorytmie Dijkstry. Na początku gotowe są jedynie terminale 0 i 1 (z długościami słowa równymi 1).
Wybieramy z kolejki symbol $g$ o najkrótszym słowie. Dla każdej reguły $r$, w której $g$ występuje po prawej stronie, uaktualniamy wartości $mut\_left[r]$ i $len[r]$ i jeśli ta pierwsza jest równa 0, to relaksujemy długość słowa $dist[g_L]$ wartością $len[r]$, gdzie $g_L$ jest nieterminalem po lewej stronie $r$.
const int N = 110; const ull infty = 1ULL<<63; int g,n,m; int mut_a[N]; int mut_left[N]; // left Bs in mutation ull len[N]; // current len of mutation vector<int> rules_b[N]; // mutations in which appear B ull dist[N]; vector<int> order; // gene order int main() { scanf("%d%d%d",&g,&n,&m); REP(i,n) { int k; scanf("%d%d",&mut_a[i],&k); REP(j,k) { int b; scanf("%d",&b); rules_b[b].push_back(i); } mut_left[i] = k; } assert(m == 0); struct cmp { bool operator()(int i, int j) const { return make_pair(dist[i], i) < make_pair(dist[j], j); } }; set<int,cmp> que; REP(i,g) dist[i] = infty; REP(i,2) { dist[i] = 1; que.insert(i); } while (!que.empty()) { int g = *que.begin(); que.erase(que.begin()); order.push_back(g); for (int r : rules_b[g]) { len[r] += dist[g]; int a = mut_a[r]; if (--mut_left[r] == 0 && len[r] < dist[a]) { auto it = que.find(a); if (it != que.end()) que.erase(it); dist[a] = len[r]; que.insert(a); } } } for (int i=2; i<g; ++i) { if (dist[i] < infty) { printf("NO %llu\n", dist[i]); } else { printf("YES\n"); } } }
Złożoność czasowa algorytmu wynosi $O(N \log N)$.
Ten algorytm też nam da kolejność topologiczną na symbolach (którą zapiszemy w tablicy $order$) oraz usunie nieterminale cyklące się. To przyda nam się w późniejszych algorytmach.
W drugim podzadaniu mamy $n=g-2$, czyli każdy nieterminal ma dokładnie jedną regułę, a więc generuje co najwyżej jedno słowo (zatem dokładnie jedno, jeśli nie mamy cyklenia się). Albo zatem to słowo będzie zawierało w sobie słowo zabronione (i wtedy odpowiedź jest YES), albo nie (i wtedy wypisujemy długość słowa).
Załóżmy na początek, że mamy również jedno słowo zabronione ($m=1$). W takim przypadku zadanie sprowadza się do problemu wyszukiwania wzorca (słowa zabronionego) w tekście (słowie generowanym przez gramatykę). Problem jest tylko taki, że tekst może być wykładniczo długi, więc standardowy algorytm wyszukiwania wzorca (nawet liniowy algorytm Knutha--Morrisa--Pratta) będzie zbyt wolny.
Niemniej jednak, algorytm KMP będzie naszym punktem wyścia. Przypomnijmy, że w tym algorytmie analizujemy kolejne prefiksy $y[0..i)$ tekstu i utrzymujemy informację (stan $p$), która oznacza, że najdłuższy sufiks $y[0..i)$, który jest jednocześnie prefiksem wzorca $x$ ma długość $p$.
Zbudujemy teraz automat wyszukujący wzorzec, w którym $A[p][c]$ oznacza, że jeśli jesteśmy w stanie $p$ i przeczytaliśmy literę $c$ (w naszym przypadku litery to terminale 0 i 1), to automat przechodzi do stanu $A[p][c]$. Innymi słowy, jeśli na prefiksie $y[0..i)$ jesteśmy w stanie $p$, to po przeczytaniu $c = y[i]$ znajdziemy się na prefiksie $y[0..i+1)$ w stanie $A[p][c]$. Automat znajduje wzorzec, jeśli kiedykolwiek znajdzie się w stanie $p = m$:
struct automaton_t { int alph; vector<int> x, ps; int m; automaton_t(const vector<int>& x) : x(x) { m = x.size() + 1; ps = vector<int>(m); ps[0] = -1; REP(i,m-1) { int p = ps[i]; while (p != -1 && x[i] != x[p]) p = ps[p]; ps[i+1] = p+1; } } int advance(int p, int c) { if (p == m-1) p = ps[p]; while (p != -1 && c != x[p]) p = ps[p]; assert(p+1 < m); return p+1; } int states() const { return m; } bool is_final(int p) { return p == m-1; } };
Tę konstrukcję możemy rozszerzyć na nieterminale gramatyki. Jeżeli jesteśmy w stanie $p$ i przeczytamy słowo generowane przez nieterminal $c$, to znajdziemy się w stanie $A[p][c]$. Interesować nas też będzie, czy podczas czytania tego słowa, przejdziemy przez stan $m$. To zapiszemy w zmiennej $F[p][c]$.
Jak zatem wyznaczyć tablicę $A[p][c]$? Przeglądamy symbole $c$ w kolejności topologicznej $order$. Jeśli $c$ jest terminalem, to stan $A[p][c]$ znajdujemy jak w algorytmie KMP i ustawiamy $F[p][c]$ na prawdę, jeśli $A[p][c] = m$.
Dla nieterminala $c$ przechodzimy po jedynej regule $c \to c_1 c_2 \ldots c_s$. Zaczynamy ze stanu $p_0 = p$ i zmieniamy go zgodnie z zasadą $p_i = A[p_{i-1}][c_i]$ dla kolejnych $1 \leq i \leq s$. Na końcu przyjmujemy $A[p][c] = p_s$. Natomiast $F[p][c]$ jest prawdą, jeśli któreś z $F[p_{i-1}][c_i]$ jest prawdą.
Przypomnijmy, że algorytm Dijkstry wyznaczył nam długości najkrótszych słów generowanych z nieterminali. Z jednoznaczności gramatyki wynika, że są to długości jedynych generowanych słów. Musimy tylko wyrzucić te nieterminale $c$, dla których $F[0][c]$ jest prawdą, bo ich słowa zawierają w sobie słowo zabronione.
Opuścimy teraz założenie o jednym słowie zabronionym -- zatem w tekście mamy teraz do wyszukania więcej niż jeden wzorzec. Ale limity w zadaniu są wystarczająco małe, żebyśmy mogli niezależnie dla każdego słowa zabronionego wyznaczyć automat wyszukujący wzorzec. (Szybsze rozwiązanie dostalibyśmy, używając algorytmu Aho--Corasick. Ale on będzie potrzebny później.)
vector<vector<int>> anti; int A[M][N], F[M][N];
REP(i,m) { int k; scanf("%d",&k); anti.push_back(vector<int>()); REP(j,k) { int c; scanf("%d",&c); anti[i].push_back(c); } } assert(n == g-2); REP(antinum,m) { automaton_t automaton(anti[antinum]); int S = automaton.states(); for (int c : order) REP(i,S) { if (c < 2) { A[i][c] = automaton.advance(i, c); F[i][c] = automaton.is_final(A[i][c]); } else { int s = i; int f = 0; for (int xx : mut[rules[c][0] /* only one */]) { f |= F[s][xx]; s = A[s][xx]; } A[i][c] = s; F[i][c] = f; } } for (int c : order) { if (F[0][c]) dist[c] = infty; } }
Teraz opuszczamy założenie o jednoznaczności gramatyki (ale nadal ustalmy jedno słowo zabronione). Zatem z jednego nieterminala może nam się wygenerować wiele słów. Tak więc startując ze stanu $p$ i dokładając nieterminal $c$, musimy przeanalizować wiele słów generowanych z $c$, o różnych długościach, po wczytaniu których możemy znaleźć się w różnych stanach (i po drodze wejść lub nie wejść do stanu $m$).
Poradzimy sobie z tym, wzbogacając naszą gramatykę o informacje o stanach automatu rozpoznającego wzorzec. Dla każdego symbolu $g$ gramatyki oraz stanów $p$ i $q$ tworzymy nowy symbol $g_{p,q}$. Idea jest taka, że z tego symbolu będą generowane te słowa $w$ generowane z $g$, dla których jeśli automat startuje ze stanu $p$, to po wczytaniu słowa $w$ znajdzie się w stanie $q$ i po drodze nigdy nie wejdzie do stanu $m$.
Potrzebne nam zatem będą reguły dla tych nowych symboli. Na początek przekształcimy gramatykę do równoważnej postaci normalnej Chomsky'ego, tzn. każdą regułę $c \to c_1 c_2 \ldots c_s$ zastępujemy zbiorem reguł $c \to c_1 c_{2..s}$, $c_{2..s} \to c_2 c_{3..s}$, $\ldots$, $c_{s-1..s} \to c_{s-1} c_s$, w których po prawej stronie stoją co najwyżej dwa symbole gramatyki.
W takim przypadku dla każdej reguły $c \to c^1 c^2$ i stanów $p,q,r$ dodajemy reguły $c_{p,q} \to c^1_{p,r} c^2_{r,q}$.
Na takiej gramatyce uruchamiamy algorytm z podzadania 1 i dla nieterminala $g$ z oryginalnej gramatyki rozważamy wszystkie słowa generowane z nieterminali $g_{0,p}$ dla wszystkich stanów $p$.
Sumaryczna długość reguł gramatyki zwiększyła się nam do $O(N M^3)$, zatem czas działania algorytmu będzie wynosił $O(N M^3 \log (NM))$:
int main() { scanf("%d%d%d",&g,&n,&m); REP(i,n) { int k; scanf("%d%d",&mut_a[i],&k); REP(j,k) { int b; scanf("%d",&b); mut[i].push_back(b); rules_b[b].push_back(i); } } // chomsky int nold = n; int originalg = g; REP(i,nold) { while (mut[i].size() > 2) { int c2 = mut[i].back(); mut[i].pop_back(); int c1 = mut[i].back(); mut[i].pop_back(); rules_b[c1].erase( find(rules_b[c1].begin(), rules_b[c1].end(), i) ); rules_b[c2].erase( find(rules_b[c2].begin(), rules_b[c2].end(), i) ); mut_a[n] = g; mut[n] = { c1, c2 }; mut[i].push_back(g); rules_b[g].push_back(i); n++; g++; } } REP(i,m) { int k; scanf("%d",&k); anti.push_back(vector<int>()); REP(j,k) { int c; scanf("%d",&c); anti[i].push_back(c); } } assert(m == 1); automaton_t automaton(anti[0]); int S = automaton.states(); int oldg = g; g = oldg + oldg * S * S; auto encode = [S,oldg](int c, int p, int q) { return (c*S + p)*S + q + oldg; }; REP(i,n) mut_left[i] = mut[i].size(); // stated nold = n; REP(i,nold) { REP(p,S) REP(q,S) { if (mut[i].size() == 1) { mut_a[n] = encode(mut_a[i], p, q); mut_left[n] = 1; rules_b[ encode(mut[i][0], p, q) ].push_back(n); n++; } else if (mut[i].size() == 2) { REP(r,S) { mut_a[n] = encode(mut_a[i], p, q); mut_left[n] = 2; rules_b[ encode(mut[i][0], p, r) ].push_back(n); rules_b[ encode(mut[i][1], r, q) ].push_back(n); n++; } } else { assert(0); } } }
W przypadku wielu słów zabronionych wystarczy, że rozszerzymy funkcjonalność automatu rozpoznającego wzorzec o rozpoznawanie wielu wzorców; reszta kodu zostanie taka sama. Możemy w tym celu użyć standardowego algorytmu Aho--Corasick:
struct aho_automaton_t { int alph; vector<vector<int>> x; vector<int> ps; int m; struct node { int prev,fin; map<int,int> children; node() : fin(0) { } }; vector<node> nodes; aho_automaton_t(const vector<vector<int>>& x) : x(x) { m = 0; nodes.push_back(node()); m++; for (auto word : x) { int no = 0; for (int c : word) { if (nodes[no].children.count(c) == 0) { nodes[no].children[c] = m; nodes.push_back(node()); m++; } no = nodes[no].children[c]; } nodes[no].fin = 1; } nodes[0].prev = -1; queue<int> que; que.push(0); while (!que.empty()) { int p = que.front(); que.pop(); for (auto x : nodes[p].children) { int c = x.first; int q = x.second; que.push(q); int z = nodes[p].prev; while (z != -1 && nodes[z].children.count(c) == 0) { z = nodes[z].prev; } if (z == -1) { nodes[q].prev = 0; } else { assert(nodes[z].children.count(c) != 0); nodes[q].prev = nodes[z].children[c]; if (nodes[nodes[q].prev].fin) nodes[q].fin = 1; } } } } int advance(int p, int c) { while (p != -1 && nodes[p].children.count(c) == 0) { p = nodes[p].prev; } if (p == -1) return 0; assert(nodes[p].children.count(c) != 0); return nodes[p].children[c]; } int states() const { return m; } bool is_final(int p) { return nodes[p].fin; } };