Cod sursa(job #1225012)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 31 august 2014 21:38:36
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <set>
#define DIM 10000011
#define ct 50011
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
char A[DIM],w[24],*p;

set<int> S;
set<int>::iterator z;
vector<int> v;
vector<pair<int,int> > h[ct+1];
vector<pair<int,int> >::iterator it;

int main(void){
    register int n,aux,q,num,k,i;
    register bool ok;
    vector<int>::iterator t;

    f>>A;
    while(f>>w){
        q=0,num=1,ok=false;
        for(p=w;*p;p++)
            q+=(*p-'a')*num,num*=3;
        S.insert(q);
    }
    k=strlen(w),n=strlen(A);

    q=0,num/=3,aux=num;
    int sol=0;
    for(i=n-1;i>=n-k;i--)
        q+=(A[i]-'a')*num,num/=3;
    if(S.find(q)!=S.end())
        h[q%ct].push_back(make_pair(q,1));
    num=aux;

    for(;i>=0;i--){
        q-=(A[i+k]-'a')*num,q*=3,q+=(A[i]-'a'),ok=false;
        if(S.find(q)==S.end())
            continue;
        for(it=h[q%ct].begin();it!=h[q%ct].end();it++)
            if(it->first==q){
                it->second++,ok=true,sol++;
                break;
            }
        if(!ok)
            h[q%ct].push_back(make_pair(q,1)),sol++;
    }

    g<<sol;
    f.close();
    g.close();
    return 0;
}