Cod sursa(job #1486158)

Utilizator enedumitruene dumitru enedumitru Data 13 septembrie 2015 22:49:24
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<fstream>
#include<vector>
#include<cstring>
#define mod 847129
#define ui unsigned int
using namespace std;
ifstream f("abc2.in"); ofstream g("abc2.out");
char s[10000010],t[25];
vector <ui> h[mod+2];
int Cautare(ui x)
{   ui i,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;
    ui a,p3[25];
    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;
}