Cod sursa(job #2634247)

Utilizator stefantagaTaga Stefan stefantaga Data 10 iulie 2020 10:53:00
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <bits/stdc++.h>
#define MOD 666013
#define baza 5
#define MOD2 1000003
#define baza2 7
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
long long put(long long a,long long b)
{
    if (b==0)
    {
        return 1;
    }
    long long rez=put(a,b/2);
    if (b%2==0)
    {
        return (rez*rez)%MOD;
    }
    return ((rez*rez)%MOD*a)%MOD;
}
long long put2(long long a,long long b)
{
    if (b==0)
    {
        return 1;
    }
    long long rez=put2(a,b/2);
    if (b%2==0)
    {
        return (rez*rez)%MOD2;
    }
    return ((rez*rez)%MOD2*a)%MOD2;
}
long long inv (long long a)
{
    return put(a,MOD+2);
}
char s[10000001],s1[25];
long long n1,nr,n,imp,val1,nr1,lung,j,sum,q,val2;
pair <int,int> fr[50005];
bool ok (int a,int b)
{
    int st=1,dr=q,mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (a<fr[mij].first)
        {
            dr=mij-1;
        }
        else
        if (a>fr[mij].first)
        {
            st=mij+1;
        }
        else
        if (a==fr[mij].first)
        {
            if (b<fr[mij].second)
            {
                dr=mij-1;
            }
            else
            if (b>fr[mij].second)
            {
                st=mij+1;
            }
            else
            {
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    f>>s;
    while (f>>s1)
    {
        n1=strlen(s1);
        nr=0;
        nr1=0;
        for (j=0;j<n1;j++)
        {
            nr=(nr*baza+(s1[j]-'a'+1))%MOD;
            nr1=(nr1*baza2+(s1[j]-'a'+1))%MOD2;
        }
        fr[++q]={nr,nr1};
        lung=n1;
    }
    sort (fr+1,fr+q+1);
    n=strlen(s);
    imp=inv(put(baza,n1));
    val1=put(baza,n1-1);
    val2=put2(baza2,n1-1);
    nr1=0;
    nr=0;
    for (j=0;j<n1;j++)
    {
        nr=(1LL*nr*baza+(s[j]-'a'+1))%MOD;
        nr1=(1LL*nr1*baza2+(s[j]-'a'+1))%MOD2;
    }
    sum=sum+ok(nr,nr1);
    for (j=1;j<n-n1+1;j++)
    {
        nr=(nr-(1LL*val1*(s[j-1]-'a'+1))%MOD+MOD)%MOD;
        nr=(1LL*nr*baza+(s[j+n1-1]-'a'+1))%MOD;
        nr1=(nr1-(1LL*val2*(s[j-1]-'a'+1))%MOD2+MOD2)%MOD2;
        nr1=(1LL*nr1*baza2+(s[j+n1-1]-'a'+1))%MOD2;
        sum=sum+ok(nr,nr1);
    }
    g<<sum;
    return 0;
}