Pagini recente » Cod sursa (job #2156806) | Cod sursa (job #1812879) | Cod sursa (job #1563028) | Cod sursa (job #628929) | Cod sursa (job #3306848)
#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;
}