Pagini recente » Cod sursa (job #1504644) | Cod sursa (job #1519725) | Cod sursa (job #853691) | Cod sursa (job #1149232) | Cod sursa (job #2223935)
#include <bits/stdc++.h>
using namespace std;
char s[10000005];
char c[25];
const int MOD1 = 100003;
const int MOD2 = 100019;
int Sol;
vector <pair <int, int> > v[MOD2 + 5];
inline void addHash(int H1, int H2, int pos){
for(auto &it : v[H2])
if(it.first == H1){++it.second; return ;}
v[H2].push_back({H1, 1});
}
inline void find(int H1, int H2){
vector <pair <int, int> > :: iterator it = v[H2].begin();
for(it; it != v[H2].end() ; ++it){
if(it->first == H1){
Sol += it->second;
v[H2].erase(it);
return ;
}
}
}
int main()
{
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
fgets(s, sizeof(s), stdin);
fgets(c, sizeof(c), stdin);
int L = strlen(s) - 1, Lc = strlen(c) - 1;
if(L < Lc){printf("0"); return 0;}
int H1 = 0, H2 = 0, p1 = 1, p2 = 1;
for(int i = 0; i < Lc ; ++i){
H1 = (H1 * 3 + s[i] - 'a' + 1) % MOD1;
H2 = (H2 * 3 + s[i] - 'a' + 1) % MOD2;
p1 = (p1 * 3) % MOD1; p2 = (p2 * 3) % MOD2;
}
addHash(H1, H2, 0);
for(int i = Lc; i < L ; ++i){
H1 = (H1 * 3 + s[i] - 'a' + 1) % MOD1;
H2 = (H2 * 3 + s[i] - 'a' + 1) % MOD2;
H1 = (H1 - p1 * (s[i - Lc] - 'a' + 1));
H2 = (H2 - p2 * (s[i - Lc] - 'a' + 1));
if(H1 < 0) H1 += MOD1;
if(H2 < 0) H2 += MOD1;
addHash(H1, H2, i - Lc + 1);
}
do{
H1 = 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;
}
find(H1, H2);
fgets(c, sizeof(c), stdin);
}while(!feof(stdin));
printf("%d", Sol);
return 0;
}