Cod sursa(job #3255553)

Utilizator timicsIoana Tamas timics Data 11 noiembrie 2024 02:07:36
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.46 kb
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define FOR(i, to) for (int i = 0; i < (to); ++i)
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<pair<int, int> > vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
#define Nmax 2000100
int N;
string s, t;
vi cnt, v;

class Aho {
public:
  static const int sigma = 26; // alphabet size 
  static const int off = 'a'; // first letter
  int nodes; // nodes
  int NR = 0; // terminal nodes

  vi tr; //
  vi term; //
  vi link; // fail edge
  vvi to; // edges

  // custom shite
  vi ind; // index of string that ends here
 
  Aho() {
    nodes = 1;
    _new_node_update();
  }

  void _new_node_update() {
    tr.pb(0);
    term.pb(0);
    link.pb(0);
    to.pb(vi(sigma, 0));
    ind.pb(0); // custom
  }
 
  void add(string &s, int val) {
    int cur = 0; // root
    for(auto c: s) {
      if(!to[cur][c - off]) {
        to[cur][c - off] = nodes++;
        _new_node_update();
      }
      cur = to[cur][c - off];
    }
    term[cur] = cur;
    tr[cur] = ++NR;

    // custom shite
    if(ind[cur] == 0) {
      ind[cur] = val;
    } else {
      v[val] = ind[cur];
    }
  }
   
  void push_links() {
    queue<int> Q;
    Q.push(0);
    while(!Q.empty()) {
      int V = Q.front();
      Q.pop();
      int U = link[V];
      if(!term[V]) term[V] = term[U];
      FOR(c, sigma) {
        if(to[V][c]) {
          link[to[V][c]] = V ? to[U][c] : 0;
          Q.push(to[V][c]);
        } else {
          to[V][c] = to[U][c];
        }
      }
    }
  }

  void process_match(int node) {
    ++cnt[ind[node]];
  }
 
  void match(string &s) {
    int cur = 0;
    for(auto c: s) {
      cur = to[cur][c-off];
      int f = cur;
      while(f) {
        if(tr[f]) {
          process_match(f);
        }
        if(f == term[f]) f = term[link[f]];
        else f = term[f];
      }
    }
  }
};

Aho aho;

int main() {
  freopen("ahocorasick.in","r",stdin);
  freopen("ahocorasick.out","w",stdout);

  cin>>s>>N;
  cnt.resize(N+1);
  v.resize(N+1);
  FOR(i, N+1) v[i] = i;

  FOR(i,N) {
    cin>>t;
    aho.add(t, i+1);
  }
  aho.push_links();
  aho.match(s);
  for(int i=1;i<=N;++i) cout<<cnt[v[i]]<<"\n";

}