Pagini recente » Cod sursa (job #875230) | Cod sursa (job #193266) | Cod sursa (job #394139) | Cod sursa (job #282210) | Cod sursa (job #3148037)
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("fast-math")
using namespace std;
const int MAXNODES = 1e6 + 2;
const int MAXEDGES = 26;
const int NMAX = 100;
ifstream fin( "ahocorasick.in" );
ofstream fout( "ahocorasick.out" );
bitset <100> endingWords[MAXNODES+1];
int state[MAXNODES+1][MAXEDGES+1];
int root, nrStates;
string words[NMAX+1];
int fail[MAXNODES+1];
int ans[NMAX+1];
void addWord( int ind ) {
int i, curState;
curState = root;
for( i = 0; i < words[ind].size(); i++ ) {
if( state[curState][words[ind][i]-'a'] == 0 )
state[curState][words[ind][i]-'a'] = nrStates++;
curState = state[curState][words[ind][i]-'a'];
}
endingWords[curState][ind] = 1;
}
void bfs() {
int i, curState;
queue <int> q;
for( i = 0; i < MAXEDGES; i++ ) {
if( state[root][i] ) {
q.push( state[root][i] );
fail[state[root][i]] = root;
}
}
while( !q.empty() ) {
auto qfront = q.front();
q.pop();
for( i = 0; i < MAXEDGES; i++ ) {
if( state[qfront][i] ) {
q.push( state[qfront][i] );
curState = qfront;
do {
curState = fail[curState];
if( state[curState][i] ) {
fail[state[qfront][i]] = state[curState][i];
endingWords[state[qfront][i]] |= endingWords[fail[state[qfront][i]]];
break;
}
else if( curState == root )
fail[state[qfront][i]] = root;
} while( curState != root );
}
}
}
}
string s;
int n;
void goThroughString() {
int i, curState, j;
curState = root;
for( i = 0; i < s.size(); i++ ) {
while( state[curState][s[i]-'a'] == 0 && curState != root )
curState = fail[curState];
if( state[curState][s[i]-'a'] != 0 )
curState = state[curState][s[i]-'a'];
if( !endingWords[curState].any() )
continue;
j = endingWords[curState]._Find_next(-1);
/*for( j = 0; j < n; j++ ) {
if( endingWords[curState][j] )
ans[j]++;
}*/
while( j != 100 ) {
ans[j]++;
j = endingWords[curState]._Find_next(j);
}
}
}
int main() {
int i;
fin >> s;
root = 1;
nrStates = 2;
fin >> n;
for( i = 0; i < n; i++ ) {
fin >> words[i];
addWord( i );
}
bfs();
goThroughString();
for( i = 0; i < n; i++ )
fout << ans[i] << "\n";
return 0;
}