Cod sursa(job #1981540)

Utilizator MKLOLDragos Ristache MKLOL Data 15 mai 2017 22:51:01
Problema Aho-Corasick Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 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 10100
#define inf 101010000
#define sigma 26
int tr[Nmax], nw[Nmax], NR, term[Nmax], len[Nmax], to[Nmax][sigma], link[Nmax], sz = 1;
map<string,int> h;
void add(string s) {
  if(h[s]) return;
  int cur = 0;
  for(auto c: s) {
    if(!to[cur][c - 'a']) {
        to[cur][c - 'a'] = sz++;
        len[to[cur][c - 'a']] = len[cur] + 1;
    }
    cur = to[cur][c - 'a'];
  }
  term[cur] = cur;
  tr[cur] = ++NR;  
  h[s]=NR;
}
 
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];
      }
    }
  }
}

string S[Nmax];
int rv[Nmax];
int main() { //6AM8-8R6M-F38B-7CY9-RF6K
  freopen("ahocorasick.in","r",stdin);
  freopen("ahocorasick.out","w",stdout);
  string s;
  cin >> s;
  int N;
  cin >> N;
  FOR(i,N) {
    string s1;
    cin >> S[i];
    add(S[i]);
  }
  push_links();
  int cur = 0;
  for(auto c : s) {    
    cur = to[cur][c-'a'];
    int f = cur;
    while(f) {
     // cout << f << endl;
      if(tr[f]) ++rv[tr[f]];
      f = link[f];
    }
    //cout << rv[1] << " ";
    
  }
  FOR(i,N) cout << rv[h[S[i]]] << "\n";
  
}