Cod sursa(job #383805)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 18 ianuarie 2010 10:15:13
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.67 kb
#include<stdio.h>
#include<math.h>
#include<vector>
#include<string.h>
#define MOD 6666013
using namespace std;
int n,nrg,f[21];
char s2[21],s[10000001];
vector <int> hash[MOD];
int find(int val)
{
    int key=val%MOD;
    int nv=hash[key].size();
    int ng=0,i;
    for(i=0;i<nv;i++)
        if(hash[key][i]==val)
        {
            ng++;
            hash[key][i]=-1;
        }
    return ng;
}
void insert(int val)
{
    int key=val%MOD;
    hash[key].push_back(val);
}

int main ()
{
    int nr,i,j,val=0,exp;
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    gets(s);
    n=strlen(s);
    while(1)
    {
        s2[0]='d';
        gets(s2);
        if(s2[0]=='d')
            break;
        nr=strlen(s2);
        f[nr]=1;
        val=0;
        for(j=0;j<nr;j++)
        {
            exp=pow(3,nr-j-1);
            if(s2[j]=='a')
                continue;
            if(s2[j]=='b')
                val+=exp;
            if(s2[j]=='c')
                val+=2*exp;
        }
        insert(val);
    }
    for(i=1;i<=20;i++)
    {
        if(f[i]==0)
            continue;
            val=0;
        for(j=0;j<i;j++)
        {
            exp=pow(3,i-j-1);
            if(s2[j]=='a')
                continue;
            if(s2[j]=='b')
                val+=exp;
            if(s2[j]=='c')
                val+=2*exp;
        }
        nrg+=find(val);

        exp=pow(3,i-1);
        for(j=i;j<n;j++)
        {
            val-=exp*((int)s[j-i]-'a');
            val*=3;
            val+=(int)(s[j]-'a');
            nrg+=find(val);
        }
    }
    printf("%d\n",nrg);
    return 0;
}