Pagini recente » Cod sursa (job #2237181) | Cod sursa (job #735655) | Cod sursa (job #1885491) | Cod sursa (job #1138404) | Cod sursa (job #2390302)
#include <bits/stdc++.h>
#define Kmax 25
#define Nmax 10000005
#define prime1 3
#define prime2 5
#define base1 666013
#define base2 100021
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
bitset <base1> vis1;
bitset <base2> vis2;
char s[Nmax],word[Kmax];
int main(){
f>>s;
int lg;
while(f>>word){
int hash1=0,hash2=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;
}
vis1[hash1]=true;
vis2[hash2]=true;
}
int ans=0,i;
int hash1=0,hash2=0;
for(i=0;s[i] and i<lg;i++){
hash1=(hash1*prime1+s[i]-'a')%base1;
hash2=(hash2*prime2+s[i]-'a')%base2;
}
if(i==lg){
if(vis1[hash1] and vis2[hash2])
++ans;
}
int diff1=1,diff2=1;
for(int j=1;j<lg;j++){
diff1=(diff1*prime1)%base1;
diff2=(diff2*prime2)%base2;
}
for(;s[i];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;
if(vis1[hash1] and vis2[hash2])
++ans;
}
g<<ans;
return 0;
}