Pagini recente » Cod sursa (job #2329721) | Cod sursa (job #1740478) | Cod sursa (job #1165989) | Cod sursa (job #3280579) | Cod sursa (job #2390307)
#include <bits/stdc++.h>
#define Kmax 25
#define prime1 2
#define prime2 5
#define prime3 7
#define base1 666012
#define base2 100021
#define base3 4722
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
bitset <base1> vis1;
bitset <base2> vis2;
bitset <base3> vis3;
char word[Kmax];
string s;
int main(){
f>>s;
int lg;
while(f>>word){
int hash1=0,hash2=0,hash3=0;
lg=0;
for(int i=0;word[i];i++){
++lg;
hash1=(hash1*prime1+word[i]-'a')%base1;
hash2=(hash2*prime2+word[i]-'a')%base2;
hash3=(hash3*prime3+word[i]-'a')%base3;
}
vis1[hash1]=true;
vis2[hash2]=true;
vis3[hash3]=true;
}
int ans=0,i;
int hash1=0,hash2=0,hash3=0;
int N=s.size();
if(N<lg){
g<<0;
return 0;
}
for(i=0;i<lg;i++){
hash1=(hash1*prime1+s[i]-'a')%base1;
hash2=(hash2*prime2+s[i]-'a')%base2;
hash3=(hash3*prime3+s[i]-'a')%base3;
}
if(i==lg){
if(vis1[hash1] and vis2[hash2] and vis3[hash3])
++ans;
}
int diff1=1,diff2=1,diff3=1;
for(int j=1;j<lg;j++){
diff1=(diff1*prime1)%base1;
diff2=(diff2*prime2)%base2;
diff3=(diff3*prime3)%base3;
}
for(;i<N;i++){
hash1=(hash1-diff1*(s[i-lg]-'a')+base1)%base1;
hash1=(hash1*prime1+s[i]-'a')%base1;
hash2=(hash2-diff2*(s[i-lg]-'a')+base2)%base2;
hash2=(hash2*prime2+s[i]-'a')%base2;
hash3=(hash3-diff3*(s[i-lg]-'a')+base3)%base3;
hash3=(hash3*prime3+s[i]-'a')%base3;
if(vis1[hash1] and vis2[hash2] and vis3[hash3])
++ans;
}
g<<ans;
return 0;
}