Cod sursa(job #344063)
/*
* 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;
list *pi, *pj;
nod()
{
fail = 0;
for(int i = 0; i < 3; ++i) next[i] = 0;
pi = pj = 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]];
}
list *p = new list(++numOfStrings);
p->next = T->pi;
T->pi = p;
if(T->pj == 0) T->pj = T->pi;
}
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(T->pi == 0 && fail->pi)
T->pi = fail->pi,
T->pj = fail->pj;
else
if(T->pi && fail->pi)
T->pj->next = fail->pi;
}
}
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);
}
}
void search(char a[], int n, bool sol[])
{
int i;
nod *T = R;
for(i = 0; i < n; ++i)
{
while(T->next[a[i]] == 0) T = T->fail;
if(T == 0) { T = R; continue;}
T = T->next[a[i]];
if(T->pi) sol[i] = 1;
}
}
char a[10000001];
bool sol[10000001];
int main()
{
freopen("abc2.in","r",stdin);
gets(a);
char x[32];
int len = 0;
while(!feof(stdin))
{
gets(x);
len = strlen(x);
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, sol);
int nsol = 0;
for(int i = 0; i < len; ++i)
if(sol[i]) ++nsol;
freopen("abc2.out","w",stdout);
printf("%d\n", nsol);
return 0;
}