Cod sursa(job #1060022)

Utilizator thewildnathNathan Wildenberg thewildnath Data 17 decembrie 2013 15:05:39
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<stdio.h>
#include<string.h>
#include<list>
using namespace std;

#define MOD1 66013
#define MOD2 10007
#define B 79

int p1,p2;
char a[10000010],aux[25];
list<int> v[MOD1+10];

inline bool sterge(const int &h1,int h2)
{
    list<int>::iterator it;
    for(it=v[h1].begin();it!=v[h1].end();++it)
        if(*it==h2)
        {

            return 1;
        }
    return 0;
}

int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    int n,l,i,h1,h2,sol=0;

    scanf("%s\n",&a);
    n=strlen(a);h1=h2=0;
    scanf("%s\n",&aux);
    l=strlen(aux);

    for(i=0;i<l;++i)
    {
        h1=(h1*B+a[i])%MOD1;
        h2=(h2*B+a[i])%MOD2;
    }
    v[h1].push_back(h2);
    p1=p2=1;
    for(i=1;i<l;++i)
    {
        p1=(p1*B)%MOD1;
        p2=(p2*B)%MOD2;
    }
    for(;i<n;++i)
    {
        h1=((h1-(a[i-l]*p1)%MOD1+MOD1)*B+a[i])%MOD1;
        h2=((h2-(a[i-l]*p2)%MOD2+MOD2)*B+a[i])%MOD2;

        v[h1].push_back(h2);
    }

    while(1)
    {
        h1=h2=0;
        for(i=0;i<l;++i)
        {
            h1=(h1*B+aux[i])%MOD1;
            h2=(h2*B+aux[i])%MOD2;
        }
        sol+=sterge(h1,h2);

        if(scanf("%s\n",&aux)==EOF)
            break;
    }

    printf("%d\n",sol);

    return 0;
}