Cod sursa(job #1447368)

Utilizator Cezar_MihalceaCezar Mihalcea Cezar_Mihalcea Data 4 iunie 2015 10:25:46
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<fstream>
#include<cstring>
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
const int N=50000,M=666019,Q=10000000;
int lst[M];
int val[N];
int urm[N];
char s[Q],p[N];
int nr=0,cnt=0;
void adauga(long long x)
{
    int r=x%M;
    nr++;
    val[nr]=x;
    urm[nr]=lst[r];
    lst[r]=nr;
}
bool cauta(long long x)
{
    int p=lst[x%M];
    while(p!=0)
    {
        if(val[p]==x)
            return true;
        p=urm[p];
    }
    return false;
}
long long codif(char *p,int k)
{
    int i;
    long long x=1;
    for(i=0;i<k;i++)
        x=x*3+(p[i]-'a');
    return x;
}
int main()
{
    char c[20];
    int k=0,rez=0,n,i;
    long long x;
    f.getline(s,Q);
    f>>c;
    k=strlen(c);
    adauga(codif(c,k));
    while(f>>c)
    {
        x=codif(c,k);
        if(!cauta(x))
            adauga(x);
    }
    n=strlen(s);
    for(i=0;i+k<n;i++)
        if(cauta(codif(s+i,k)))
            rez++;
    g<<rez;
    return 0;
}