Pagini recente » Cod sursa (job #2515581) | Cod sursa (job #2325609) | Cod sursa (job #2999602) | Cod sursa (job #3134374) | Cod sursa (job #1690618)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ahocorasick.in");
ofstream fout("ahocorasick.out");
#define MAX 1000010
char c[MAX], c2[10010];
struct node{
int val = 0;
vector <int> v;
node *fiu[26] = {0}, *fail = 0;
} *R, *Q[MAX];
void introdu(node *R, char c[], int i)
{
if(c[0] == 0)
{
R->v.push_back(i);
return;
}
if(R->fiu[c[0] - 'a'] == 0)
{
R->fiu[c[0] - 'a'] = new node;
}
introdu(R->fiu[c[0] - 'a'], c + 1, i);
}
int st, dr, rez[103];
void bfs()
{
st = 1;
dr = 0;
Q[++dr] = R;
R->fail = R;
while(dr - st + 1)
{
node* nod = Q[st++];
for(int i = 0 ; i < 26 ; i++)
{
node *son = nod->fiu[i];
if(son)
{
Q[++dr] = son;
son->fail = nod->fail;
while(son->fail != R && son->fail->fiu[i] == 0)
son->fail = son->fail->fail;
if(son->fail->fiu[i] && son != son->fail->fiu[i])
son->fail = son->fail->fiu[i];
}
}
// cout << nod << " " << nod->fail << "\n";
}
}
int main()
{
R = new node;
int n, i;
fin >> c;
fin >> n;
for(i = 1 ; i <= n ; i++)
{
fin >> c2;
introdu(R, c2, i);
}
bfs();
node *nod = R;
for(i = 0 ; c[i] ; i++)
{
while(nod != R && nod->fiu[c[i] - 'a'] == 0)
{
nod = nod->fail;
}
if(nod->fiu[c[i] - 'a'])
nod = nod->fiu[c[i] - 'a'];
nod->val++;
}
//cout << "\n";
for(i = dr ; i >= 1 ; i--)
{
nod = Q[i];
nod->fail->val += nod->val;
// cout << nod << " " << nod->val << "\n";
for(int j = 0 ; j < nod->v.size() ; j++)
{
rez[nod->v[j]] = nod->val;
}
}
for(i = 1 ; i <= n ; i++)
{
fout << rez[i] << "\n";
}
return 0;
}