Pagini recente » Rating Robert Cimpeanu (ZyNNoMe) | Istoria paginii utilizator/lacitek | Cod sursa (job #1282117) | Cod sursa (job #2214747) | Cod sursa (job #2223964)
#include <bits/stdc++.h>
using namespace std;
char s[10000005];
char c[25];
const int MOD1 = 100003;
const int MOD2 = 100019;
int Sol, Lc;
vector <int> v[MOD2 + 5];
inline bool find(int H1, int H2){
for(auto it : v[H2])
if(it == H1) return 1;
return 0;
}
inline void addHash(int H1, int H2){
if(!find(H1, H2)) v[H2].push_back(H1);
}
int main()
{
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
scanf("%s\n", s);
while(!feof(stdin)){
scanf("%s\n", c);
Lc = strlen(c);
int H1 = 0, H2 = 0;
for(int i = 0; i < Lc ; ++i){
H1 = (H1 * 3 + c[i] - 'a' + 1) % MOD1;
H2 = (H2 * 3 + c[i] - 'a' + 1) % MOD2;
}
addHash(H1, H2);
}
int L = strlen(s);
if(L < Lc){printf("0"); return 0;}
int H1 = 0, H2 = 0, p1 = 1, p2 = 1;
for(int i = 0; i < Lc ; ++i){
if(i != 0) p1 = (p1 * 3) % MOD1, p2 = (p2 * 3) % MOD2;
H1 = (H1 * 3 + s[i] - 'a' + 1) % MOD1;
H2 = (H2 * 3 + s[i] - 'a' + 1) % MOD2;
}
Sol += find(H1, H2);
for(int i = Lc; i < L ; ++i){
H1 = ((H1 - (s[i - Lc] - 'a' + 1) * p1 % MOD1 + MOD1) % MOD1 * 3 + s[i] - 'a' + 1) % MOD1;
H2 = ((H2 - (s[i - Lc] - 'a' + 1) * p2 % MOD2 + MOD2) % MOD2 * 3 + s[i] - 'a' + 1) % MOD2;
Sol += find(H1, H2);
}
printf("%d", Sol);
return 0;
}