Cod sursa(job #2076090)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 26 noiembrie 2017 10:10:37
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#define rose 666013
#include<bits/stdc++.h>
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
long long nrcur;
char c[10000003];
int len,ln,sol;
int R;
struct pl
{
    vector<int>v;
};
pl rest[rose];
int lun[rose];
char q[25];
int main()
{
    f>>c;
    R=strlen(c);
    while(f>>q)
    {
        long long p3=1;
        nrcur=0;
        if(ln==0)
            ln=strlen(q);
        for(int j=ln-1;j>=0;--j)
            nrcur+=p3*(q[j]-'a'),p3*=3;
        int R=nrcur%rose;
        rest[R].v.push_back(nrcur);
        ++lun[R];
    }
    for(int i=0;i<rose;++i)
        if(lun[i])
            sort(rest[i].v.begin(),rest[i].v.end());
    long long p3=1;
    for(int j=0;j<=R-ln;++j)
    {
        if(j==0){
            for(int k=ln-1;k>=0;--k)
                nrcur+=p3*(c[k]-'a'),p3*=3;
            p3/=3;
        }
        else
        {
            nrcur-=p3*(c[j-1]-'a');
            nrcur*=3;
            nrcur+=(c[j+ln-1]-'a');
        }
        int R=nrcur%rose;
        int b=0;
        int e=lun[R]-1;
        while(b<=e)
        {
            int m=(b+e)/2;
            if(rest[R].v[m]==nrcur)
            {
                ++sol;
                break;
            }
            else
                if(rest[R].v[m]>nrcur)
                    e=m-1;
                else
                    b=m+1;
        }
    }
    g<<sol;
    return 0;
}