Cod sursa(job #2137364)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 20 februarie 2018 19:12:28
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.58 kb
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using ll = long long;
using pii = pair<int, int>;
#define dbg(x) cerr<<#x": "<<(x)<<'\n'
#define dbg_v(x, n) {cerr<<#x"[]: ";for(long long _=0;_<n;++_)cerr<<(x)[_]<<' ';cerr<<'\n';}
#define all(v) v.begin(), v.end()
#define INF 2000000010
#define MOD 1000000007
#define ST_SIZE 1048600
#define QMAX 
#define SMAX 1000010
#define NMAX 110
#define LMAX 10010
#define SIGMA 26

struct info {
	int cnt;
	char ch;
	info *fth, *link;
	info *next[SIGMA];
	bool isNext[SIGMA];
	
	info(info *_fth, char _ch) {
		cnt = 0;
		ch = _ch - 'a';
		fth = _fth;
		link = nullptr;
		memset(next, 0, sizeof next);
		memset(isNext, 0, sizeof(isNext));
	}
};

char a[SMAX];
char s[LMAX];
info *Q[SMAX], *cuv[NMAX];

info* add(info *node, char *s) {
	for(; *s; ++s) {
		if(!node->next[*s - 'a']) {
			node->next[*s - 'a'] = new info(node, *s);
			node->isNext[*s - 'a'] = true;
		}
		node = node->next[*s - 'a'];
	}
	
	return node;
}

int getCnt(info *node, char *s) {
	for(; *s; ++s) node = node->next[*s - 'a'];
	
	return node->cnt;
}

info* getLink(info *node);
info* go(info *node, char ch);
void bfs(info *root);

void print(info *node, char ch, string indent = "") {
	cout << indent << ' ' << ch << ' ' << node->cnt << '\n';
	
	for(int i = 0; i < SIGMA; ++i)
		if(node->next[i])
			print(node->next[i], 'a' + i, indent + '\t');
}

int main()
{
	freopen("ahocorasick.in", "r", stdin);
	freopen("ahocorasick.out", "w", stdout);
	
	int i, n;
	info *root, *node;
	
	root = new info(nullptr, 0);
	
	scanf("%s %d", a, &n);
	
	for(i = 0; i < n; ++i) {
		scanf(" %s", s);
		cuv[i] = add(root, s);
	}
	
	for(node = root, i = 0; a[i]; ++i) {
		node = go(node, a[i] - 'a');
		++node->cnt;
	}
	
	//print(root, 0);
	bfs(root);
	//print(root, 0);
	
	for(i = 0; i < n; ++i)
		printf("%d\n", cuv[i]->cnt);
	
	return 0;
}

info* getLink(info *node) {
	if(node->link) return node->link;
	if(!node->fth) return node->link = node;
	if(!node->fth->fth) return node->link = node->fth;
	
	return node->link = go(getLink(node->fth), node->ch);
}

info* go(info *node, char ch) {
	if(node->next[ch]) return node->next[ch] = node->next[ch];
	if(!node->fth) return node->next[ch] = node;
	
	return node->next[ch] = go(getLink(node), ch);
}

void bfs(info *root) {
	int i, l, r;
	
	for(Q[0] = root, l = r = 0; l <= r; ++l) {
		for(i = 0; i < SIGMA; ++i)
			if(Q[l]->isNext[i])
				Q[++r] = Q[l]->next[i];
	}
	
	for(i = r; i > 0; --i)
		getLink(Q[i])->cnt += Q[i]->cnt;
}