Cod sursa(job #2225819)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 28 iulie 2018 13:30:24
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define MOD1 107547
#define MOD2 47298
using namespace std;
char s[10000005],cc[25];
vector <int> v[MOD1+2];
int elem;
inline bool cauta (int x,int y){
    int i;
    for (i=0;i<v[x].size();i++)
        if (v[x][i]==y)
            return 1;
    return 0;
}
int main()
{
    FILE *fin=fopen ("abc2.in","r");
    FILE *fout=fopen ("abc2.out","w");
    int i,l,sol,nr1,nr2,p31,p32,ls;
    fgets (s,10000001,fin);
    elem=0;
    while (fgets (cc,25,fin)){
        l=strlen(cc)-1;
        nr1=nr2=0;
        for (i=0;i<l;i++){
            nr1=(nr1*3+(cc[i]-'a'))%MOD1;
            nr2=(nr2*3+(cc[i]-'a'))%MOD2;
        }
        if (!cauta (nr1,nr2))
            v[nr1].push_back(nr2);
    }
    ls=strlen(s)-1;
    if (ls<l){
        fprintf (fout,"0");
        return 0;
    }
    l=i;
    p31=p32=1;
    nr1=nr2=0;
    sol=0;
    for (i=0;i<l;i++){
        if (i){
            p31=(p31*3)%MOD1;
            p32=(p32*3)%MOD2;
        }
        nr1=(nr1*3+(s[i]-'a'))%MOD1;
        nr2=(nr2*3+(s[i]-'a'))%MOD2;
    }
    sol+=cauta (nr1,nr2);
    for (i=l;i<ls;i++){
        nr1=(((nr1-p31*(s[i-l]-'a'))%MOD1+MOD1)*3+(s[i]-'a'))%MOD1;
        nr2=(((nr2-p32*(s[i-l]-'a'))%MOD2+MOD2)*3+(s[i]-'a'))%MOD2;
        sol+=cauta (nr1,nr2);
    }
    fprintf (fout,"%d",sol);
    return 0;
}