Cod sursa(job #2487205)

Utilizator PetyAlexandru Peticaru Pety Data 4 noiembrie 2019 10:51:22
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.01 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin ("ahocorasick.in");
ofstream fout ("ahocorasick.out");

struct Trie {
  int nr;
  //vector<Trie*>son;
  Trie* fii[26];
  Trie *fail;
  Trie () {
    nr = 0;
    fail = NULL;
    for (int i = 0; i < 26; i++)
      fii[i] = NULL;
  }
} *root, *Nod[102];

Trie* add (string s, int i) {
  Trie* p = root;
  for (int i = 0; i < s.size(); i++) {
    if (p -> fii[s[i] - 'a'] == NULL)
      p -> fii[s[i] - 'a'] = new Trie;
    p = p -> fii[s[i] - 'a'];
  }
  Nod[i] = p;
  return p;
}

vector<Trie*>v;


void antiBFS (Trie *nod) {
  for (int i = v.size() - 1; i >= 0; i--)
    v[i] -> fail -> nr += v[i] -> nr;
}


int n;
string s, a;

int main()
{
  fin >> s >> n;
  root = new Trie;
  for (int i = 1; i <= n; i++) {
    fin >> a;
    add(a, i);
  }
  queue<Trie*>q;
  root -> fail = NULL;
  for (int i = 0; i < 26; i++) {
    if (root -> fii[i] != NULL) {
      root -> fii[i] -> fail = root;
      v.push_back(root -> fii[i]);
      //root-> son.push_back(root-> fii[i]);
      q.push(root -> fii[i]);
    }
  }
  while (!q.empty()) {
    Trie* nod = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (nod -> fii[i] != NULL) {
        q.push(nod -> fii[i]);
        v.push_back(nod -> fii[i]);
        Trie* aux = nod -> fail;
        while (aux != root && aux -> fii[i] == NULL)
          aux = aux -> fail;
        if (aux -> fii[i] != NULL)
          nod -> fii[i] -> fail = aux -> fii[i];
        else
          nod -> fii[i] -> fail = root;
        //nod -> fii[i] -> fail -> son.push_back(nod -> fii[i]);
      }
    }
  }
  Trie* p = root;
  for (int i = 0; i < s.size(); i++) {
    while(p != root && p -> fii[s[i] - 'a'] == NULL)
      p = p -> fail;
    if (p -> fii[s[i] - 'a'] != NULL)
      p = p -> fii[s[i] - 'a'];
    else
      p = root;
    if (p != root)
      p -> nr++;
  }
  antiBFS(root);
  for (int i = 1; i <= n; i++)
    fout << Nod[i] -> nr << "\n";
  return 0;
}