Cod sursa(job #2899872)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 9 mai 2022 13:26:13
Problema Aho-Corasick Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.09 kb
/// always:
#include <cstdio>
#include <string>

/// optional:
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>

bool home = 1;
using namespace std;

const string TASKNAME="ahocorasick";
int n;
string s;

struct Vertex{
  Vertex* kids[26];
  Vertex* fail;
  vector<int> inds;
  int sol;

  Vertex() {
    for (int i=0;i<26;i++) kids[i]=nullptr;
    fail=nullptr;
    sol=0;
  }
};

Vertex* root=new Vertex;
int sol[123];

signed main() {
#ifdef INFOARENA
  home = 0;
#endif

  if(!home) {
    freopen((TASKNAME + ".in").c_str(), "r", stdin);
    freopen((TASKNAME + ".out").c_str(), "w", stdout);
  }else{
    freopen ("I_am_iron_man", "r", stdin);
  }

  cin>>s>>n;
  for (int i=1;i<=n;i++) {
    string word;
    cin>>word;
    Vertex* current=root;
    for (auto &ch:word){
      int x=ch-'a';
      assert(0<=x&&x<26);
      if(!current->kids[x]) current->kids[x]=new Vertex;
      current=current->kids[x];
    }
    current->inds.push_back(i);
  }
  vector<Vertex*> topo={root};
  root->fail=root;
  for (int i=0;i<(int)topo.size();i++) {
    Vertex* current=topo[i];
    for (int x=0;x<26;x++) {
      if(current->kids[x]) {
        Vertex* fail_vertex=current->fail;
        while (fail_vertex!=root&&!fail_vertex->kids[x]) fail_vertex=fail_vertex->fail;
        if(i>0&&fail_vertex->kids[x]) fail_vertex=fail_vertex->kids[x];
        current->kids[x]->fail=fail_vertex;
        topo.push_back(current->kids[x]);
      }
    }
  }

  Vertex* current=root;

  for (auto &ch:s){
    int x=ch-'a';
    assert(0<=x&&x<26);
    while (current!=root&&!current->kids[x]) current=current->fail;
    if (current->kids[x]) current=current->kids[x];

    current->sol++;
  }

  for (int i=(int)topo.size()-1;i>=0;i--) {
    Vertex* current=topo[i];
    current->fail->sol+=current->sol;
    for (auto &i:current->inds) {
      sol[i]=current->sol;
    }
  }

  for (int i=1;i<=n;i++) {
    cout<<sol[i]<<"\n";
  }



  /**for (auto &current:topo) {
    cout<<current->s<<" -> "<<current->fail->s<<"\n";
  }**/
}