Cod sursa(job #1093093)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 27 ianuarie 2014 18:53:23
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 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<pair<ll,int> > V[MOD];
vector<pair<ll,int> >::iterator it;
void Add(long long x)
{
    r=x%MOD;
	for(it=V[r].begin();it!=V[r].end();it++)
        if(it->first==x) {it->second++; return;}
    V[r].push_back(make_pair(x,1));
}
int Find(long long x)
{
    r=x%MOD;
	for(it=V[r].begin();it!=V[r].end();it++)
        if(it->first==x)
        {
            int c=it->second;
            it->second=0;
            return c;
        }
    return 0;
}
int main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	fgets(S+1,NMAX,stdin);
	fgets(A+1,DMAX,stdin);
	N=strlen(A+1)-1;
	M=strlen(S+1)-1;
	for(B=1,i=1;i<=N;i++)
	{
	    cod=cod*3+S[i]-'a';
	    if(i>1) B*=3;
	}
	Add(cod);
	for(;i<=M;i++)
	{
	    cod=cod-1LL*B*(S[i-N]-'a');
	    cod=cod*3+S[i]-'a';
	    Add(cod);
	}
	for(cod=0,i=1;i<=N;i++)
	    cod=cod*3+A[i]-'a';
    sol+=Find(cod);
    while(fgets(A+1,DMAX,stdin))
    {
        for(cod=0,i=1;i<=N;i++)
            cod=cod*3+A[i]-'a';
        sol+=Find(cod);
    }
    printf("%lld\n",sol);
	return 0;
}