Cod sursa(job #2137276)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 20 februarie 2018 18:22:28
Problema Aho-Corasick Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 2.36 kb
#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 NMAX 110
#define LMAX 10010
#define SIGMA 26

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

string a;
char s[NMAX][LMAX];

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

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()
{
	ifstream cin("ahocorasick.in");
	ofstream cout("ahocorasick.out");
	
	int i, n;
	info *root, *node;
	
	root = new info(nullptr, 0);
	
	cin >> a;
	
	(cin >> n).ignore();
	for(i = 0; i < n; ++i) {
		cin >> s[i];
		add(root, s[i]);
	}
	
	for(node = root, i = 0; i < a.size(); ++i) {
		node = go(node, a[i]);
		++node->cnt;
	}
	
	//print(root, 0);
	bfs(root);
	//print(root, 0);
	
	for(i = 0; i < n; ++i)
		cout << getCnt(root, s[i]) << '\n';
	
	return 0;
}

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

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

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