Pagini recente » Cod sursa (job #2315867) | Cod sursa (job #57085) | Cod sursa (job #108416) | Cod sursa (job #2450095) | Cod sursa (job #908708)
Cod sursa(job #908708)
#include <fstream>
#include <vector>
#include <cstring>
#define MOD 666013
using namespace std;
char S[10000003];
char cuvant[23];
vector < unsigned int > Hash[MOD];
unsigned int n,m;
ifstream f("abc2.in");
ofstream g("abc2.out");
void citesc(){
f >> S;
n = strlen(S);
f >> cuvant;
m = strlen(cuvant);
}
inline void Add(int X){
unsigned int key = X%MOD;
Hash[key].push_back(X);
}
inline short Search(unsigned int X){
unsigned int key = X%MOD;
for(vector <unsigned int >::iterator it = Hash[key].begin();it!=Hash[key].end();++it)
if(*it == X)
return 1;
return 0;
}
inline int Hashing(char *cuvant,unsigned int m){
unsigned int P = 0;
for(register unsigned int i=0;i<m;++i)
P = (P*3 + cuvant[i] - 'a');
return P;
}
inline void solve(){
unsigned int putere = 1;
unsigned int T=0,P=0,nr=0;
P = Hashing(cuvant,m);
Hash[P%MOD].push_back(P);
while(f >> cuvant){
P = Hashing(cuvant,m);
Hash[P%MOD].push_back(P);
}
for(register unsigned int i=1;i<m;++i)
putere*=3;
T = Hashing(S,m);
nr+=Search(T);
for(register unsigned int i=0;i<=n-m;++i){
T = (T- (S[i]-'a') *putere)*3 + (S[i+m]-'a');
nr+=Search(T);
}
g << nr;
}
int main(){
citesc();
solve();
return 0;
}