Pagini recente » Cod sursa (job #770952) | Cod sursa (job #2922605) | Cod sursa (job #2923799) | Cod sursa (job #717434) | Cod sursa (job #1668624)
#include<cstdio>
#include<stack>
#include<queue>
#include<cstring>
using namespace std;
const int L=1000000;
const int M=100000;
const int N=100;
const int SIGMA=30;
struct Node{
public:
vector<int>w;
Node* v[SIGMA];
Node* fail;
int nr;
Node(){
w.clear();
for(int i=0;i<SIGMA;i++)
v[i]=NULL;
nr=0;
}
};
stack<Node*>st;
queue<Node*>q;
int res[N+1];
Node *T=new Node;
char s[L+1];
char ss[M+1];
int n;
void set_fail(Node* dad,int c){
Node*son=dad->v[c];
if(dad==T){
son->fail=T;
return;
}
Node*curr=dad->fail;
while(curr->v[c]==NULL&&curr!=T)
curr=curr->fail;
if(curr->v[c]!=NULL)
son->fail=curr->v[c];
else
son->fail=T;
}
void bfs(){
q.push(T);
while(!q.empty()){
Node* dad=q.front();
st.push(dad);
q.pop();
for(int i=0;i<SIGMA;i++){
Node*son=dad->v[i];
if(son!=NULL){
set_fail(dad,i);
q.push(son);
}
}
}
}
void aho_corasick(){
int l=strlen(s);
Node*curr=T;
for(int i=0;i<l;i++){
int c=s[i]-'a';
while(curr->v[c]==NULL&&curr!=T)
curr=curr->fail;
if(curr->v[c]!=NULL){
curr=curr->v[c];
curr->nr++;
}
}
}
int main(){
freopen("ahocorasick.in","r",stdin);
freopen("ahocorasick.out","w",stdout);
gets(s);
scanf("%d\n",&n);
for(int i=1;i<=n;i++){
gets(ss);
int m=strlen(ss);
Node*curr=T;
for(int j=0;j<m;j++){
int c=ss[j]-'a';
if(curr->v[c]==NULL)
curr->v[c]=new Node();
curr=curr->v[c];
}
curr->w.push_back(i);
}
bfs();
aho_corasick();
T->fail=T;
while(!st.empty()){
Node* dad=st.top();
st.pop();
dad->fail->nr+=dad->nr;
for(unsigned int i=0;i<dad->w.size();i++)
res[dad->w[i]]+=dad->nr;
}
for(int i=1;i<=n;i++)
printf("%d\n",res[i]);
return 0;
}