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$ .

Brak słów zabronionych

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 $d i s t [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 $m u t_l e f t [r]$ oraz aktualną długość słowa $l e n [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 $m u t_l e f t [r]$ i $l e n [r]$ i jeśli ta pierwsza jest równa 0, to relaksujemy długość słowa $d i s t [g_{L}]$ wartością $l e n [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 $o r d e r$ ) oraz usunie nieterminale cyklące się. To przyda nam się w późniejszych algorytmach.

Jednoznaczność

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 $o r d e r$ . 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} \dots 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;
    }
  }

Jedno słowo zabronione

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} \dots c_{s}$ zastępujemy zbiorem reguł $c \to c_{1} c_{2. . s}$ , $c_{2. . s} \to c_{2} c_{3. . s}$ , $\dots$ , $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_{p, r}^{1} c_{r, q}^{2}$ .

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 (N M))$ :

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);
      }
    }
  }

Rozwiązanie wzorcowe

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;
  }
};