Cod sursa(job #1225899)

Utilizator buzu.tudor67Tudor Buzu buzu.tudor67 Data 3 septembrie 2014 22:45:24
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<cstring>
#include<vector>
using namespace std;

const int BASE = 3;
const int MODULO = 666013;
const int max_l = 10000007;
const int lung_max_cuvant = 25;

vector <long long> h[MODULO];
char cuvant[lung_max_cuvant];
char s[max_l];
int lung,sol;

void inserare(long long x){
     int zona=x%MODULO;
     if(zona<0) zona=-zona;
     h[zona].push_back(x);
}

int cautare(long long x){
    int zona=x%MODULO;
    if(zona<0) zona=-zona;
    for(int j=0;j<(int)h[zona].size();j++)
      if(h[zona][j]==x) return j;
      
    return -1;
}

void prelucrare_inserare(char *s, int n){
     int i;
     long long x=0;
     
     for(i=0;i<n;i++)
        {
         int cifra=s[i]-'a';
         x=x*BASE+cifra;             
        }
     
     int k=cautare(x);
     if(k==-1) inserare(x);
}

void rezolvare(char *s, int n){
     int i; long long x=0;
     int putere=1;
     
     for(i=1;i<=lung;i++) putere*=BASE;
     
     for(i=0;i<lung;i++)
        {
         int cifra=s[i]-'a';
         x=x*BASE+cifra;
        } 
     
     if(cautare(x)!=-1) sol++;
     for(i=lung;i<n;i++)
        {
         int cifra=s[i]-'a';
         x=x*BASE-((s[i-lung]-'a')*putere)+cifra;
         if(cautare(x)!=-1) sol++;               
        }
}

int main(void){
    assert(freopen("abc2.in","r",stdin));
    assert(freopen("abc2.out","w",stdout));
    
    assert(fgets(s,max_l,stdin));
    
    assert(fgets(cuvant,lung_max_cuvant,stdin));
    lung=strlen(cuvant)-1; 
    prelucrare_inserare(cuvant,lung);
    while(fgets(cuvant,lung_max_cuvant,stdin)) prelucrare_inserare(cuvant,lung);
    
    rezolvare(s,strlen(s)-1);
    
    printf("%d",sol);
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}