Cod sursa(job #2292813)

Utilizator MaarcellKurt Godel Maarcell Data 30 noiembrie 2018 00:11:36
Problema Aho-Corasick Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.24 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <ctime>
#include <unordered_map>
#include <iomanip>
#include <complex>
#include <cassert>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define deb(a) cerr<< #a << "= " << (a)<<"\n";

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;
typedef complex<double> base;
typedef vector<int> vi;
typedef pair<int,int> pii;

template<class T> ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream; }
ll fpow(ll x, ll p, ll m){ll r=1; for (;p;p>>=1){ if (p&1) r=r*x%m; x=x*x%m; } return r;}
ll inv(ll a, ll b){ return a<2 ? a : ((a-inv(b%a,a))*b+1)/a%b; }
int gcd(int a, int b){ if (!b) return a; return gcd(b,a%b);}
ll gcd(ll a, ll b){ if (!b) return a; return gcd(b,a%b);}


int N,to[1000010][26],fail[1000010],root,T,cnt[1000100],q[1000100];
string s;
int nid[120];

int ins(int nod, string &s, int p, int id){
	if (nod==0)
		nod=++T;
	
	if (p==(int)s.length()){
		nid[id]=nod;
		return nod;
	}
	
	to[nod][s[p]-'a']=ins(to[nod][s[p]-'a'],s,p+1,id);
	
	return nod;
}

void compfail(){
	fail[1]=1;
	int K=1;
	q[1]=1;
	
	for (int p=1; p<=T; p++){
		int x=q[p];
		
		for (int k=0; k<26; k++)
			if (to[x][k]){
				int nod=to[x][k];
				int cr=fail[x];
				
				while (cr!=1 && to[cr][k]==0)
					cr=fail[cr];
					
				if (to[cr][k] && to[cr][k]!=nod)
					cr=to[cr][k];
					
				fail[nod]=cr;
				q[++K]=nod;
			}
	}
}

void prop(){
	for (int i=T; i>1; i--)
		cnt[fail[q[i]]]+=cnt[q[i]];
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	ifstream cin("ahocorasick.in");
	ofstream cout("ahocorasick.out");
	cin >> s;
	
	int i;
	root = 1;
	T=1;
	cin >> N;
	for (i=1; i<=N; i++){
		string w;
		cin >> w;
		
		root = ins(root,w,0,i);
	}
	
	compfail();
	
	int cr=1;
	for (i=0; i<(int)s.length(); i++){
		while (cr!=1 && !to[cr][s[i]-'a'])
			cr=fail[cr];
		
	
		if (to[cr][s[i]-'a'])
			cr=to[cr][s[i]-'a'];
			
		cnt[cr]++;
		
	}
		
	prop();
	
	for (i=1; i<=N; i++)
		cout << cnt[nid[i]] << "\n";
}