Pagini recente » Cod sursa (job #1061466) | Cod sursa (job #1832161) | Cod sursa (job #2564548) | Cod sursa (job #1212260) | Cod sursa (job #1308907)
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
using namespace std;
char text[10000009];
char cuvant[25];
int i,n,j;
struct trie{
trie *fiu[3],*fail;
int nr;
trie(){
memset(fiu,0,sizeof(fiu));
nr = 0; fail = NULL;
}
};
trie *t = new trie,*q[400000000],*ult,*nod;
//trie *punct_final_cuvant[50050]
map< string , trie* > m;
void insert(trie *nod,char *c){
if( *c == '\0' ){
//punct_final_cuvant[i] = nod;
ult = nod;
return ;
}
if( nod->fiu[ *c - 'a' ] == NULL ) nod->fiu[ *c - 'a' ] = new trie;
insert( nod->fiu[ *c - 'a' ] , c+1 );
}
int main()
{
freopen("abc2.in" , "r" , stdin);
freopen("abc2.out", "w" , stdout);
scanf("%s", text);
while( !feof(stdin) ){
scanf("%s", cuvant);
if( m.find( string(cuvant) ) != m.end() ) continue;
++i;
//insert( t , cuvant );
j = 0; nod = t;
while( cuvant[j] != '\0' ){
if( nod->fiu[ cuvant[j] - 'a' ] == NULL ) nod->fiu[ cuvant[j] - 'a' ] = new trie;
nod = nod->fiu[ cuvant[j] - 'a' ];
++j;
}
m[ string(cuvant) ] = nod;
}/////////////////////////////////////////////////////////////
n = i;
trie *nod, *fail;
t->fail=t;
int inc , fin;
for( q[inc=fin=1] = t; inc <= fin ; ++inc ){
nod = q[inc];
for(i=0 ; i <3 ; ++i)
if( nod->fiu[i] ){
for(fail = nod->fail; fail != t && fail->fiu[i] == 0; fail = fail->fail);
if( fail->fiu[i] != NULL && fail != nod ) fail = fail->fiu[i];
nod->fiu[i]->fail = fail;
q[++fin] = nod->fiu[i];
} /////////////////////////////////////////////////////
} ////////////////////////////////////////////////////////////
trie *p = t;
t->fail = NULL;
int len = strlen(text) , k;
for(i = 0;i < len; ++i){
k = text[i] - 'a';
for( ; p->fiu[k] == NULL && p != t; p = p->fail);
if( p->fiu[k] ) p = p->fiu[k];
++p->nr;
}
for(i = fin ; i ; --i){
nod=q[i];
if( nod->fail != NULL ) nod->fail->nr += nod->nr;
}
int sum = 0;
for( map< string , trie* >::iterator it = m.begin() ; it != m.end() ; ++it )
sum += it->second->nr;
printf("%d",sum);
return 0;
}