Cod sursa(job #98625)
// chestii grele
#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#define RUN_IT
using namespace std;
int N, M, L, ret;
char A[10111111], cuv[50111][22];
clock_t start, end;
void clock_it( string x )
{
#ifndef RUN_IT
clock_t at = clock();
cout << x << " = " << 1.0 * ( at - start ) / CLOCKS_PER_SEC << endl;
#endif
}
#define V 3
struct node
{
char term;
node * to[ V ], *f;
node()
{
for( int i = 0; i < V; ++i )
to[i] = NULL;
term = 0;
}
} * R;
void t_init()
{
R = new node();
}
void t_add_word( char * s )
{
node * at = R;
for( int i = 0; i < M; ++i )
{
if( at->to[ s[i] ] )
at = at->to[ s[i] ];
else
{
node * n = new node();
at->to[ s[i] ] = n;
at = n;
}
}
at->term = 1;
}
void print_trie( node * n, int pos)
{
int nr(0);
for( int x = 0; x < V; ++x )
if( n->to[x] )
{
if( nr )
cout << string( pos, ' ' );
cout << (int)(x);
print_trie( n->to[x], pos + 1 );
++nr;
}
if( !nr )
cout << endl;
}
#define MAX_SZ 888999
//int f[MAX_SZ];
//char out[MAX_SZ];
//int g[MAX_SZ][V];
node * Q[MAX_SZ];
int nr_word, nr_state;
/*
void df( node * n )
{
for( int x = 0; x < V; x++ )
{
if( n->to[x] )
{
g[ n->id ][ x ] = n->to[x]->id;
df( n->to[x] );
}
else
{
if( n->id == 0 ) // root
g[ 0 ][ x ] = 0;
else
g[ n->id ][ x ] = -1;
}
}
out[ n->id ] = n->term;
}
*/
void build_automata()
{
#ifndef RUN_IT
cout << "Nr_state = " << nr_state << endl;
#endif
clock_it( "Resizing" );
clock_it( "df" );
int left = 0, right = -1;
for( int x = 0; x < V; ++x )
if( R->to[x] )
R->to[x]->f = R,
Q[ ++right ] = R->to[x];
clock_it( "graph" );
for( ; left <= right; left++ )
{
node * r = Q[ left ], *u, *v;
for( int x = 0; x < V; ++x )
if( (u=r->to[x]) ) // u is the son of r with edge x
{
Q[ ++right ] = u;
v = r->f;
while( !v->to[x] )
v = v->f;
u->f = v->to[x];
u->term |= u->f->term;
}
}
clock_it( "queue" );
}
void gen()
{
srand(23);
freopen("abc2.in", "w", stdout);
L = 10000000, N = 50000, M = 20;
for( int i = 0; i < L; i++ )
printf("%c", (char)( 'a' + rand() % 3 ) ); printf("\n");
string aux( ' ', M );
for( int c = 0; c < N; c++ )
{
for( int i = 0; i < M; i++ )
aux[i] = (char)( 'a' + rand() % 3 );
for( int i = 0; i < M; i++ )
printf("%c", aux[i] ); printf("\n");
}
}
int main()
{
// gen();
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
start = clock();
int i, j, l, k;
gets( A );
L = strlen( A );
N = 0;
while( gets( cuv[++N] ) );
--N;
if( N == 0 )
{
printf("0\n");
return 0;
}
M = strlen(cuv[1]);
if( M > L )
{
printf("0\n");
return 0;
}
for( l = 0; l < L; l++ )
A[l] -= 'a';
for( i = 1; i <= N; i++ )
for( l = 0; l < M; l++ )
cuv[i][l] -= 'a';
clock_it( "reading" );
t_init();
for( int i = 1; i <= N; i++ )
t_add_word( cuv[i] );
build_automata();
// cout << MyAC.process_string() << endl;
int q = 0; int x;
node * m = R;
clock_it( "starting string processing" );
for( i = 0; i < L; ++i )
{
x = (int)A[i];
for( ; !m->to[x]; m = m->f );
m = m->to[x];
ret += (int)m->term;
}
cout << ret << endl;
clock_it( "total" );
return 0;
}