Cod sursa(job #3306848)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 14 august 2025 15:41:34
Problema Aho-Corasick Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct trie{
	trie *v[26], *kmp = nullptr;
	//string drum;
	int f = 0;
	trie(){
		int i;
		for( i = 0; i < 26; i++ ){
			v[i] = nullptr;
		}
	}
};
trie *root = new trie(), *x, *k, *capat[105];
vector <trie *> stiva;
vector <string> v;
trie *insert( trie *node, string s ){
	int i, x;
	for( i = 0; i < s.size(); i++ ){
		x = s[i] - 'a';
		if( node->v[x] == nullptr ){
			node->v[x] = new trie();
		}
		//node->v[x]->drum = node->drum + s[i];
		node = node->v[x];
	}
	return node;
}
void solve( trie* node, string s ){
	int i, x;
	for( i = 0; i < s.size(); i++ ){
		x = s[i] - 'a';
		while( node != root && node->v[x] == nullptr ){
			node = node->kmp;
		}
		if( node->v[x] != nullptr ){
			node = node->v[x];
		}
		//cout << s[i] << ' ' << node->drum << '\n';
		node->f++;
	}
}
int main(){
	int n, i;
	string s, a;
	ifstream fin( "ahocorasick.in" );
	ofstream fout( "ahocorasick.out" );
	fin >> s >> n;
	for( i = 0; i < n; i++ ){
		fin >> a;
		v.push_back( a );
		capat[i] = insert( root, a );
		//cout << capat[i]->drum << '\n';
	}
	root->kmp = root;
	queue <trie *> q;
	q.push( root );
	while( q.empty() == false ){
		x = q.front();
		q.pop();
		stiva.push_back( x );
		for( i = 0; i < 26; i++ ){
			if( x->v[i] != nullptr ){
				k = x->kmp;
				while( k != nullptr && k->v[i] == nullptr ){
					k = k->kmp;
				}
				if( k != nullptr ){
					x->v[i]->kmp = k->v[i];
				}
				if( k == nullptr || x->v[i]->kmp == x->v[i] ){
					x->v[i]->kmp = root;
				}
				q.push( x->v[i] );
			}
		}
	}
	solve( root, s );
	for( i = stiva.size() - 1; i >= 0; i-- ){
		x = stiva[i];
		x->kmp->f += x->f;
	}
	for( i = 0; i < v.size(); i++ ){
		fout << capat[i]->f << '\n';
	}
	return 0;
}