Cod sursa(job #3255269)

Utilizator timicsIoana Tamas timics Data 9 noiembrie 2024 21:31:09
Problema Aho-Corasick Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.27 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, val;

class Aho {
public:
  int sigma = 26; // alphabet size 
  int off = 'a';
  int to[Nmax][26]; // todo: change / resize
  int sz = 1; // nodes
  int NR = 0; // terminal nodes
  int tr[Nmax], term[Nmax];
  int link[Nmax]; // fail edge
  int ind[Nmax];
 
  Aho(int sg, int offset) {sigma = sg; off = offset;}
  Aho() {}
 
  void add(string &s, int i) {
    int cur = 0; // root
    for(auto c: s) {
      if(!to[cur][c - off]) {
          to[cur][c - off] = sz++;
      }
      cur = to[cur][c - off];
    }
    term[cur] = cur;
    tr[cur] = ++NR;
    if(ind[cur] == 0) {
      ind[cur] = i;
    } else {
      val[i] = 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(int c = 0; c < sigma; c++) {
        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 stuff_on_match(int f) {
    ++cnt[ind[f]];
  }
 
  void match(string &s) {
    int cur = 0;
    for(auto c: s) {
      cur = to[cur][c-off];
      int f = cur;
      while(f) {
        if(tr[f]) {
          stuff_on_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);
  val.resize(N+1);
  FOR(i, N+1) val[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[val[i]]<<"\n";

}