Cod sursa(job #2452328)

Utilizator RadianElevenAdrian Ariotn RadianEleven Data 30 august 2019 14:46:38
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.58 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 mod=mod=1000000007;
long long abmodc(long long a,long long b)
{
     //   a^b mod c

   if(a % mod == 0)
		return 0;

	int res=1;

	while(b)
	{
		if(b%2==1)
			res = (res * a) % mod;

		b /= 2;
		a = (a * a) % mod;
	}

	return res;
}
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;
    int pow=1;
    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';
            if(op==0)
                pow*=3;

        }
        cek[op+1]=a;
      //  g<<a<<" "<<t<<"\n ";
        op++;
    }


    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(1,op+1, b)!=-1)
                nr++;

        }
    }
    g<<nr;

    return 0;
}