Cod sursa(job #1093104)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 27 ianuarie 2014 18:58:32
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<cstdio>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
const int NMAX = 10000005;
const int DMAX = 25;
const int MOD = 100009;
int N,M,i,r; ll cod,B,sol;
char S[NMAX],A[DMAX];
vector<ll> V[MOD];
vector<ll>::iterator it;
void Add(long long x)
{
    r=x%MOD;
    V[r].push_back(x);
}
void Find(long long x)
{
    r=x%MOD;
	for(it=V[r].begin();it!=V[r].end();it++)
        if(*it==x) {sol++; return;}
}
int main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	fgets(S+1,NMAX,stdin);
	M=strlen(S+1)-1;
	while(fgets(A+1,DMAX,stdin))
    {
        N=strlen(A+1)-1;
        for(cod=0,i=1;i<=N;i++)
            cod=cod*3+A[i]-'a';
        Add(cod);
    }
	for(B=1,cod=0,i=1;i<=N;i++)
	{
	    cod=cod*3+S[i]-'a';
	    if(i>1) B*=3;
	}
    Find(cod);
	for(;i<=M;i++)
	{
	    cod=cod-1LL*B*(S[i-N]-'a');
	    cod=cod*3+S[i]-'a';
	    Find(cod);
	}
    printf("%lld\n",sol);
	return 0;
}