Cod sursa(job #749045)

Utilizator MagnvsDaniel Constantin Anghel Magnvs Data 15 mai 2012 17:47:05
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>

using namespace std;

typedef unsigned int uint;
const int mod=5003;

char l[10000010],ch[30];
vector <uint> hash[mod];

void ins(uint x){
    int aux;
    
    aux=x%mod;
    for (vector <uint>::iterator it=hash[aux].begin(); 
        it!=hash[aux].end(); ++it){
        
        if (*it==x){
            return;
        }
    }

    hash[aux].push_back(x);
}

bool find(uint x){
    uint aux;

    aux=x%mod;
    for (vector <uint>::iterator it=hash[aux].begin();
        it!=hash[aux].end(); ++it){

        if (*it==x){
            return 1;
        }
    }

    return 0;
}

int main()
{
    uint m,n,i,j,aux=0,sol=0,x=0;
    
    assert(freopen("abc2.in","r",stdin));
    assert(freopen("abc2.out","w",stdout));
    l[0]=' ';
    fgets(l+1,10000005,stdin);
    n=strlen(l)-2;
    fprintf(stderr, "%u\n", n);
    fgets(ch,25,stdin);
    m=strlen(ch)-1;
    fprintf(stderr, "%u\n", m);
    for (i=0;i<m;++i)
        aux=aux*3+ch[i]-'a';
    i=1;
    while (!feof(stdin))
    {
        ++i;
        aux=0;
        fgets(ch,25,stdin);
        for (j=0;j<m;++j)
            aux=aux*3+ch[j]-'a';
        ins(aux);
        fprintf(stderr, "%u\n", aux);
    }
    fprintf(stderr, "%u\n", i);
    for (aux=1,i=1;i<m;++i)
    {
        aux*=3;
        x=x*3+l[i]-'a';
    }
    

    for (j=1;j<=n-m+1;++j)
    {
        x=(x-(x/aux)*aux)*3+l[j+m-1]-'a';
        
        if (find(x)){
            ++sol;
        }
    }
    printf("%u\n",sol);
    return 0;
}