Cod sursa(job #1315473)

Utilizator OctaDuiu Octavian Octa Data 12 ianuarie 2015 20:45:26
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include<fstream>
#include<vector>
#include<string>
#define mod 666013
using namespace std;

ifstream f("abc2.in");
ofstream g("abc2.out");

vector < unsigned int > v[mod];
string S, s;
int n, count, i;

void insert(unsigned int x)
{
    int list=x%mod;
    vector< unsigned int >::iterator it;

    for(it=v[list].begin();it!=v[list].end();++it)
        if(*it==x) return;

  v[list].push_back(x);
}

inline bool find(unsigned int x)
{
    int list=x%mod;
    vector< unsigned int >::iterator it;

    for(it=v[list].begin();it!=v[list].end();++it)
        if(*it==x) return true;

 return false;
}

int main()
{
    getline(f,S);

    while(getline(f,s))
    {
        n=s.size();
        unsigned int x=0 ;
        for(i=0;i<n;++i) x=x*3+s[i]-'a';

      insert(x);
    }

    int l=S.size();
    unsigned int x=0, p=1;

    for(i=0;i<n;++i)
    {
        x=x*3+S[i]-'a';
        p=p*3;
    }

    p/=3;
    count+=find(x);

    for(i=n;i<l;++i)
    {
        x-=p*(S[i-n]-'a');
        x=x*3+S[i]-'a';
        count+=find(x);
    }

    g<<count<<"\n";

  return 0;
}