Pagini recente » Cod sursa (job #1958782) | Cod sursa (job #1345021) | Cod sursa (job #2791425) | Cod sursa (job #1440413) | Cod sursa (job #344073)
Cod sursa(job #344073)
/*
* http://infoarena.ro/problema/abc2
* @author: Mircea Dima
* Aho Corasik O(n *L + m)
*/
#include <cstdio>
#include <queue>
using namespace std;
struct list
{
int v;
list *next;
list(){ v = 0; next = 0;}
list(int _v){v = _v; next = 0;}
};
struct nod
{
nod *next[3];
nod *fail;
bool ok;
nod()
{
fail = 0;
for(int i = 0; i < 3; ++i) next[i] = 0;
ok = 0;
}
};
nod *R = new nod();
int numOfStrings;
void insert(nod *T, char a[], int n)
{
int i;
for(i = 0; i < n; ++i)
{
if(T->next[a[i]] == 0)
T->next[a[i]] = new nod();
T = T->next[a[i]];
}
T->ok = 1;
}
inline void updateNode(nod *T, nod *father, int c)
{
nod *p = father->fail;
while(p && p->next[c] == 0)
p = p->fail;
if(p == 0) T->fail = R;
else T->fail = p->next[c];
nod *fail = T->fail;
if(T != fail)
{
if(fail->ok) T->ok = 1;
}
}
void buildAutomata()
{
queue<nod*> Q;
int i;
nod *T = R;
for(i = 0; i < 3; ++i)
if(T->next[i])
Q.push(T->next[i]),
T->next[i]->fail = R;
while(!Q.empty())
{
T = Q.front();
Q.pop();
for(i = 0; i < 3; ++i)
if(T->next[i])
Q.push(T->next[i]),
updateNode(T->next[i], T, i);
}
}
int nrSol;
int Len;
void search(char a[], int n)
{
int i;
nod *T = R;
for(i = 0; i < n; ++i)
{
while(T && T->next[a[i]] == 0) T = T->fail;
if(T == 0) { T = R;continue; }
T = T->next[a[i]];
if(T->ok) ++nrSol;
}
}
char a[10000001];
int main()
{
freopen("abc2.in","r",stdin);
gets(a);
char x[32];
int len = 0;
while(!feof(stdin))
{
gets(x);
len = strlen(x);
Len = len;
for(int i = len -1; i >= 0; --i)
x[i] -= 'a';
insert(R, x, len);
}
buildAutomata();
len = strlen(a);
for(int i = 0; i < len; ++i)
a[i] -= 'a';
search(a, len);
freopen("abc2.out","w",stdout);
printf("%d\n", nrSol);
return 0;
}