Cod sursa(job #1225154)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 1 septembrie 2014 02:35:28
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 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=q*3+(*p-'a');
        S.insert(q);
    }
    k=strlen(w),n=strlen(A);

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

    for(;*p;p++){
        q=(q-(*(p-k)-'a')*num)*3+(*p-'a');
        if(S.find(q)==S.end())
            continue;
        ok=false;
        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;
}