Pagini recente » Cod sursa (job #1462517) | Cod sursa (job #1115438) | Cod sursa (job #2753319) | Cod sursa (job #293320) | Cod sursa (job #100817)
Cod sursa(job #100817)
#include<stdio.h>
#include<string.h>
#define maxl 1024*1024*10
#define maxn 1024*1024
char text[maxl],*sf,*sf2;
long nod[maxn][3], n ,last = 1;
long nod2[maxn][9];
char text2[maxl];
long test(long end)
{
long rez =0;
long poz = 1;
char *unde = text;
char *unde2 = text;
for( ; sf - unde2 >= n; ++unde2)
{
poz = 1;
unde = unde2;
while( (unde - unde2 < n) )
{
poz = nod[poz][ *unde ];
++unde;
}
if(poz) ++ rez;
}
return rez;
}
long test2(long end)
{
long rez =0;
long poz = 1;
char *unde = text2;
char *unde2 = text2;
++end;
for( ; end--; ++unde2)
{
poz = 1;
unde = unde2;
while( (unde - unde2 < n - 1) )
{
poz = nod2[poz][ *unde ];
unde+=2;
}
if(unde - unde2 <n)
poz = nod[poz][*unde/3];
if(poz) ++rez;
}
return rez;
}
void baga(char *sir,long poz,long h)
{
if( h > n) return;
if( nod[poz][ sir[0]-'a' ] != 0 )
{
baga( sir + 1, nod[poz][sir[0] -'a'], h+1 );
return ;
}
for ( long i = h; i <= n; ++i)
{
nod[poz][ sir[i-h]-'a' ] = ++last;
poz = last;
}
}
void fa()
{
for( long i = 1; i <= last; ++i)
{
for ( long j = 0; j < 9; ++j)
nod2[i][j] = nod[ nod[i][j/3]][j%3];
}
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
char sir[32];
scanf("%s",text);
//for( long i =0 ; i < 10000000; ++i)
//text[i] = 'a';
long ok = 0;
while( scanf("%s",sir) == 1)
{
if( !ok)
n = strlen(sir);
baga(sir,1,1);
ok = 1;
}
sf = text + strlen(text);
// sf2 = text2 + strlen(text);
long x = strlen(text) - n;
for( long i = 0; i < n +x ; ++i)
text[i]-='a';
for( long i = 0; i < n + x-1; ++i)
{
text2[i] = text[i]*3 + text[i+1];
}
long rez = 0;
//return 0;
fa();
//rez+= test(x);
rez += test2(x);
printf("%ld\n",rez);
return 0 ;
}