Cod sursa(job #1499734)

Utilizator stoianmihailStoian Mihail stoianmihail Data 11 octombrie 2015 00:36:19
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <iostream>
#include <cstring>
const int Nadejde=10000005;
const int MOD=50001;
const int Smerenie=25;
typedef struct{
  unsigned int v;
  int next;
} list;
list l[MOD];
int N, M, adj[MOD], buff;
char s[Smerenie], antique[Nadejde];
unsigned int threes[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401};
unsigned int hash(){
  unsigned int h=0;
  for(int i=0;i<M;i++){
    h=((h<<1)+h+s[i]-'a');
  }
  return h;
}
int find(unsigned int val){
  int pos;
  for (pos=adj[val%MOD];pos&&l[pos].v!=val;pos=l[pos].next);
  return pos;
}
void add(unsigned int val){
  if(!find(val)){
    int h=val%MOD;
    l[++buff].v=val;
    l[buff].next=adj[h];
    adj[h]=buff;
  }
}
int main(){
  std::ifstream in("abc2.in");
  in>>antique;
  N=strlen(antique);
  while(in>>s){
    M=strlen(s);
    add(hash());
  }
  in.close();
  std::ofstream out("abc2.out");
  unsigned int h=0;
  int i=0,count=0;
  while(i<M-1){
    h=((h<<1)+h+antique[i++]-'a');
  }
  while(i<N){
    h=((h <<1)+h+antique[i]-'a');
    count+=(find(h)>0);
    h-=(threes[M-1]*(antique[++i-M]-'a'));
  }
  out<<count<<"\n";
  out.close();
  /// Multumim Doamne!
  std::cout<<"Doamne ajuta!\n";
  return 0;
}