Pagini recente » Cod sursa (job #2223082) | Cod sursa (job #1471651) | Cod sursa (job #1151979) | Cod sursa (job #2819924) | Cod sursa (job #527684)
Cod sursa(job #527684)
#include<stdio.h>
#include<algorithm>
using namespace std;
#define ui unsigned int
FILE*f=fopen("abc2.in","r");
FILE*g=fopen("abc2.out","w");
int Rez,Lc,i,N,k,step;
ui Nr,W[50005],P;
char C[25],A[10000005];
void transf ( char *C ){
Nr = 0;
for ( int i = 1 ; i <= Lc ; ++i ){
Nr = Nr * 3 + C[i] - 'a' ;
}
}
inline int cautbin ( ui x ){
int i,stp = step;
for ( i = 1 ; stp ; stp >>= 1 ){
if ( i + stp <= k && W[i + stp] <= x )
i += stp;
}
return W[i] == x ;
}
int main () {
fscanf(f,"%s\n",A);
N = strlen ( A ) - 1;
fgets(C + 1,25,f);
for ( i = 1 ; C[i] >= 'a' && C[i] <= 'z' ; ++i ) ;
Lc = i - 1;
transf(C);
W[++k] = Nr;
while ( fgets( C + 1 , 25 , f ) ){
transf(C);
W[++k] = Nr;
}
for ( i = 0 ; i < Lc ; ++i )
C[i + 1] = A[i];
for ( i = 0 , P = 1 ; i < Lc - 1 ; ++i ) P = P * 3;
sort(W+1,W+k+1);
for (step = 1; step < k ; step <<= 1 );
transf(C);
if ( cautbin(Nr) )
++Rez;
for ( i = Lc ; i <= N ; ++i ){
Nr -= ( P * ( A[ i - Lc ] - 'a' ) );
Nr = Nr * 3 + A[i] - 'a' ;
if ( cautbin(Nr) )
++Rez;
}
fprintf(g,"%d",Rez);
fclose(f);
fclose(g);
return 0;
}