Cod sursa(job #2388561)

Utilizator NeredesinI am not real Neredesin Data 26 martie 2019 10:35:45
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <cstring>
#include <vector>

#define Xp 50003

using namespace std;

ifstream in("abc2.in");
ofstream out("abc2.out");

int nr,i,l,n,j;

unsigned int a,q[23];

char w[10000012],c[24];

vector <unsigned int> M[Xp+2];

bool caut(unsigned int jeg)
{
    int r=jeg%Xp,z=M[jeg%Xp].size();

    for(j=0; j<z; ++j)
        if(M[r][j]==jeg)
            return 1;
    return 0;
}

int main()
{
    in>>(w+1);

    l=strlen(w+1);

    q[1]=1;

    for(i=2; i<=20; ++i)
        q[i]=q[i-1]*3;

    while(in>>(c+1))
    {
        n=strlen(c+1);
        for(i=1,a=0; i<=n; ++i)
            a=a+q[i]*(c[i]-'a');
        M[a%Xp].push_back(a);
    }

    for(i=1,a=0; i<=n; ++i)
        a=a+q[i]*(w[i]-'a');

    nr+=caut(a);

    for(i=n+1; i<=l; ++i)
    {
        a/=3;

        a=a+q[n]*(w[i]-'a');

        nr+=caut(a);
    }

    out<<nr;

    return 0;
}