Cod sursa(job #519877)

Utilizator S7012MYPetru Trimbitas S7012MY Data 6 ianuarie 2011 18:50:58
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define DL 10000005
#define DN 30
#define DB 50005
#define ui unsigned int
using namespace std;

char s[DL],cuv[DN];
int n,m,nrc,stp;
ui v[DB];

int cb(ui cuv) {
	int step=stp, p=1;
	for (;step; step>>=1)
		if (p+step<=nrc && v[p+step]<=cuv) p+=step;
	return v[p]==cuv;
}


int main() {
	freopen("abc2.in", "r", stdin);
	freopen("abc2.out", "w", stdout);
	fgets(s, DL, stdin);
	n=strlen(s)-1;
	while (fgets(cuv, DN, stdin)) {
		m=strlen(cuv)-1;
		ui cod=0;
		for(int i=0; i<m; ++i)
			cod=cod*3+cuv[i]-'a';
		v[++nrc]=cod;
	}
	sort(v+1, v+nrc+1);
	ui cod=0,pow=1,sol=0;
	for (int i=1;i<m; ++i) pow *= 3;
    for(stp=1;2*stp<nrc; stp<<=1 );
	for (int i=0; i<m; ++i)
		cod=cod*3 + s[i]-'a';
    sol+=cb(cod);
	for(int i=m; i<n; ++i) {
		cod-=pow*(s[i-m]-'a');
		cod=cod*3+s[i]-'a';
        sol+=cb(cod);
	}
	printf("%d\n", sol);
}