Cod sursa(job #1837322)

Utilizator vancea.catalincatalin vancea.catalin Data 29 decembrie 2016 14:59:28
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<algorithm>
#include<iostream>
#include<fstream>
#include<string>
#include<cstring>
#include<vector>
#define DN 10000100
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");

int ls,ls1,r=0;
unsigned int k1,p=1;
vector<unsigned int> v;
string s1;
char s[DN];

inline void cauta(unsigned int val)
{
    int start=0,stop=v.size()-1,m;
    while(start<stop)
    {
        m=((start+stop)>>1);
        if(v[m]<val)
            start=m+1;
        else
            stop=m;
    }
    r+=(v[start]==val);
}

int main()
{
    int i,j,c;
    fin.get(s,DN,10);fin.get();
    //cout<<s<<"\n";
    ls=strlen(s);
    while(fin>>s1)
    {
        ls1=s1.size();
        k1=0;
        for(j=0;j<ls1;j++)
        {
            c=(s1[j]-'a');
            k1=3*k1+c;
        }
        v.push_back(k1);
    }
    sort(v.begin(),v.end());

    k1=0;
    if(ls1<=ls)
    {
        for(i=0;i<ls1;i++)
        {
            if(i>0) p=p*3;
            c=(s[i]-'a');
            k1=3*k1+c;
        }
        cauta(k1);
        for(i=ls1;i<ls;i++)
        {
            c=(s[i]-'a');
            while(k1>=p) k1=k1-p;
            k1=3*k1+c;
            cauta(k1);
        }
    }
    fout<<r;
}