Pagini recente » Cod sursa (job #2133817) | Cod sursa (job #2230556) | Cod sursa (job #2582695) | Cod sursa (job #1351381) | Cod sursa (job #471721)
Cod sursa(job #471721)
#include<stdio.h>
#include<queue>
using namespace std;
#define FIN "abc2.in"
#define FOUT "abc2.out"
#define NMAX 10000003
#define LMAX 31
struct trie
{
bool T;
trie *NEXT[3];
trie* UP;
trie()
{
T = false;
NEXT[0] = NULL;
NEXT[1] = NULL;
NEXT[2] = NULL;
UP = NULL;
}
};
typedef trie* Nod;
Nod ROOT;
int N,rez = 0 ;
char SIR[NMAX];
char TEMP[31];
queue<Nod> Q;
void insert( Nod &nod , char* s )
{
if ( *s == '\n' )
{
nod -> T = true;
return;
}
if( !nod -> NEXT[*s - 'a']) nod -> NEXT[*s - 'a'] = new trie;
insert(nod -> NEXT[*s - 'a'] , s + 1 );
}
void construct()
{
ROOT -> UP = ROOT;
for(int i = 0 ; i <= 2 ; ++i)
if( ROOT -> NEXT[i] ) Q.push(ROOT -> NEXT[i]) , ROOT -> NEXT[i] -> UP = ROOT;
while(! Q.empty())
{
Nod aux = Q.front();
Q.pop();
for(int i = 0 ;i <= 2 ; ++i)
if( aux -> NEXT[i])
{
Q.push(aux -> NEXT[i]);
Nod v = aux -> UP;
while( !v -> NEXT[i] && v != ROOT ) v = v -> UP;
if(v -> NEXT [i] == NULL) aux -> NEXT[i] -> UP = ROOT;
else aux -> NEXT[i] -> UP = v -> NEXT[i];
}
}
}
int solve()
{
int poz = 0;
Nod act = ROOT;
while(SIR[poz] != '\n')
{
if( act == ROOT && !act -> NEXT[SIR[poz] - 'a']) poz++;
if( !act -> NEXT[SIR[poz] - 'a'])
act = act -> UP;
else
{ act = act -> NEXT[SIR[poz] - 'a'], poz++;
if(act -> T) rez ++;
}
}
return rez;
}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
fgets(SIR , NMAX , stdin);
ROOT = new trie;
while(fgets(TEMP , LMAX , stdin)>0 )
{
insert(ROOT , TEMP);
}
construct();
printf("%d",solve());
return 0;
}