Cod sursa(job #2038455)

Utilizator danstefanDamian Dan Stefan danstefan Data 13 octombrie 2017 18:03:30
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;
long long m,n,MOD=90907,lu,pu,i,cp,nr,j,ans;
char st[10000010],stt[40];
vector<int>h[90907];
int main()
{
    ifstream f ("abc2.in");
    ofstream g ("abc2.out");
    f>>st+1;
    lu=strlen(st+1);
    f>>stt+1;
    m=strlen(stt+1);
    pu=1;
    for(i=1; i<=m; ++i)pu*=3;
    cp=pu;
    for(i=1; i<=m; ++i)
    {
        nr+=pu*(stt[i]-'a');
        pu/=3;
    }
    h[nr%MOD].push_back(nr);
    while(f>>stt+1)
    {
        nr=0;
        pu=cp;
        for(i=1; i<=m; ++i)
        {
            nr+=pu*(stt[i]-'a');
            pu/=3;
        }
        h[nr%MOD].push_back(nr);
    }
    nr=0;
    pu=cp;
    for(i=1; i<=m; ++i)
    {
        nr+=pu*(st[i]-'a');
        pu/=3;
    }
    for(i=0; i<h[nr%MOD].size(); ++i)
        if(h[nr%MOD][i]==nr)
        {
            ++ans;
            break;
        }
    for(i=m+1; i<=lu; ++i)
    {
        nr-=cp*(st[i-m]-'a');
        nr+=(st[i]-'a');
        nr*=3;
        for(j=0; j<h[nr%MOD].size(); ++j)
            if(h[nr%MOD][j]==nr)
            {
                ++ans;
                break;
            }
    }
    g<<ans<<'\n';
    return 0;
}