Pagini recente » Cod sursa (job #2537295) | Cod sursa (job #61700) | Cod sursa (job #3281809) | Cod sursa (job #2157899) | Cod sursa (job #1499734)
#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;
}