Pagini recente » Cod sursa (job #1519316) | Cod sursa (job #2708548) | Cod sursa (job #2811027) | Cod sursa (job #3286477) | Cod sursa (job #3148033)
#include <bits/stdc++.h>
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;
for( j = 0; j < n; j++ ) {
if( endingWords[curState][j] )
ans[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;
}