Cod sursa(job #2452324)

Utilizator RadianElevenAdrian Ariotn RadianEleven Data 30 august 2019 14:31:54
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
ifstream f ("abc2.in");
ofstream g ("abc2.out");
string s;
string t;
long long a,b;
//vector<long long > vek;
long long cek[50009];

int binarySearch(int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;


        if (cek[mid]== x)
            return mid;

        if (cek[mid] > x)
            return binarySearch(l, mid - 1, x);


        return binarySearch(mid + 1, r, x);
    }

    return -1;
}
long long  lenstr, texlen;
int main()
{
    f>>s;
    int op=0;
    while(f>>t)
    {
        lenstr=t.size();
        a=0;
        for(long long  i=0;i<=t.size()-1;++i)
        {
            a*=3;
            a+=t.at(i)-'a';


        }
        cek[op+1]=a;
      //  g<<a<<" "<<t<<"\n ";
        op++;
    }
    int pow=1;
    for(int i=0;i<lenstr;++i)
    {
        pow*=3;
    }
    sort(cek+1, cek+op+1);
    texlen=s.size();
    long long nr=0;
    b=0;
    for(long long  i=0;i<texlen;++i)
    {

        b*=3;
        b+=s.at(i)-'a';
        b%=pow;
        if(i>=lenstr-1)
        {
                 //   g<<"b-> "<<b<<" "<<s<<"\n";
            if(binarySearch(0,op, b)!=-1)
                nr++;

        }
    }
    g<<nr;

    return 0;
}