Cod sursa(job #1486154)

Utilizator enedumitruene dumitru enedumitru Data 13 septembrie 2015 22:41:44
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include<fstream>
#include<vector>
#include<cstring>
#define mod 847129
using namespace std;
ifstream f("abc2.in"); ofstream g("abc2.out");
unsigned int a,p3[25];
char s[10000010],t[25];
vector <unsigned int> h[mod+2];
int Cautare(unsigned int x)
{   unsigned int i;
    int r=x%mod;
    for(i=0;i<h[r].size();i++)
        if(h[r][i]==x) return 1;
    return 0;
}
int main()
{   f>>(s+1);
    int i,m,n=strlen(s+1),nr=0;
    p3[1]=1;
    for(i=2;i<=20;i++) p3[i]=p3[i-1]*3;
    while(f>>(t+1))
    {   m=strlen(t+1);
        a=0;
        for(i=1;i<=m;i++) a=a+p3[i]*(t[i]-97);
        if(!Cautare(a)) h[a%mod].push_back(a);
    }
    a=0;
    for(i=1;i<=m;i++) a=a+p3[i]*(s[i]-97);
    nr+=Cautare(a);
    for(i=m+1;i<=n;i++)
    {   a/=3;
        a=a+p3[m]*(s[i]-97);
        nr+= Cautare(a);
    }
    g<<nr<<"\n"; g.close(); return 0;
}