Pagini recente » Cod sursa (job #13028) | Cod sursa (job #2026324) | Cod sursa (job #3042220) | Cod sursa (job #2078454) | Cod sursa (job #2364751)
#include <bits/stdc++.h>
#define Nmax 105
#define Amax 1000005
#define Lmax 10005
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
struct ACnode
{
vector <int> ends;
ACnode *fail;
ACnode *nxt[26];
ACnode()
{
for(int i = 0; i < 26; i++)
nxt[i] = NULL;
fail = NULL;
}
};
ACnode *root;
int N;
int ans[Nmax];
char C[Amax], w[Lmax];
void insert(char *w, int idx)
{
int N = strlen(w + 1);
ACnode *currNode = root;
for(int i = 1; i <= N; i++)
{
if(currNode -> nxt[w[i] - 'a'] == NULL)
currNode -> nxt[w[i] - 'a'] = new ACnode;
currNode = currNode -> nxt[w[i] - 'a'];
}
currNode -> ends.push_back(idx);
}
void DoFail(ACnode *root)
{
queue < ACnode* > Q;
root -> fail = root;
for(int i = 0; i < 26; i++)
if(root -> nxt[i] != NULL)
{
root -> nxt[i] -> fail = root;
Q.push(root -> nxt[i]);
}
while(!Q.empty())
{
ACnode *node = Q.front();
Q.pop();
for(int i = 0; i < 26; i++)
if(node -> nxt[i] != NULL)
{
ACnode *F = node -> fail;
while(F != root && F -> nxt[i] == NULL)
F = F -> fail;
if(F -> nxt[i] != NULL)
F = F -> nxt[i];
node -> nxt[i] -> fail = F;
for(auto it : F -> ends)
node -> nxt[i] -> ends.push_back(it);
Q.push(node -> nxt[i]);
}
}
}
int main()
{
fin >> (C + 1);
fin >> N;
root = new ACnode;
for(int i = 1; i <= N; i++)
{
fin >> (w + 1);
insert(w, i);
}
DoFail(root);
int L = strlen(C + 1);
ACnode *curr = root;
for(int i = 1; i <= L; i++)
{
while(curr != root && curr -> nxt[C[i] - 'a'] == NULL)
curr = curr -> fail;
if(curr -> nxt[C[i] - 'a'] != NULL)
curr = curr -> nxt[C[i] - 'a'];
for(auto it : curr -> ends)
ans[it]++;
}
for(int i = 1; i <= N; i++)
fout << ans[i] << "\n";
return 0;
}