Cod sursa(job #2188542)

Utilizator NeredesinI am not real Neredesin Data 27 martie 2018 10:56:39
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>
#define Nmax 101
using namespace std;

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

int n,rez[Nmax];
string S,c;

struct trie {
  trie *in[26],*fail;
  vector<int> P;
  int val;
  trie() {
    val = 0;
    memset(in,0,sizeof(in));
    fail = NULL;
  }
}*T;

vector<trie*> C;

void add(int poz) {
  trie *nod = T;
  for (int i=0;i<c.size();i++) {
    if (nod->in[c[i]-'a']==NULL)
      nod->in[c[i]-'a'] = new trie();
    nod = nod->in[c[i]-'a'];
  }
  nod->P.push_back(poz);
}

void bfs() {
  C.push_back(T);
  T->fail = T;
  for (int k=0;k<C.size();k++) {
    for (int i=0;i<26;i++)
      if (C[k]->in[i]!=NULL) {
        trie *nod = C[k]->fail;
        while (nod->in[i]==NULL && nod!=T)
          nod = nod->fail;
        if (nod->in[i]!=NULL && nod->in[i]!=C[k]->in[i])
          nod = nod->in[i];
        C[k]->in[i]->fail = nod;
        C.push_back(C[k]->in[i]);
      }
    }
}

void bfs2() {
  for (int i=C.size()-1;i>=0;i--) {
    C[i]->fail->val += C[i]->val;
    for (int j=0;j<C[i]->P.size();j++)
      rez[C[i]->P[j]] += C[i]->val;
  }
}

int main()
{
  T = new trie();
  in>>S;
  in>>n;
  for (int i=1;i<=n;i++) {
    in>>c;
    add(i);
  }

  bfs();
  trie *nod = T;
  for (int i=0;i<S.size();i++) {
    while (nod->in[S[i]-'a']==NULL && nod!=T)
      nod = nod->fail;
    if (nod->in[S[i]-'a']!=NULL)
      nod = nod->in[S[i]-'a'];
    nod->val++;
  }
  bfs2();
  for (int i=1;i<=n;i++)
    out<<rez[i]<<'\n';

  in.close();
  out.close();
  return 0;
}