Pagini recente » Rating ygsepoywepoj (Marin7) | Cod sursa (job #1704493) | Monitorul de evaluare | Cod sursa (job #1094546) | Cod sursa (job #1764849)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
const int NMax = 5005;
const int MOD = 100007;
//ifstream fin("abc2.in");
//ofstream fout("abc2.out");
vector < pair < ui, int > > Hash[MOD];
inline void Insert(ui x){
int n = x % MOD;
vector < pair < ui, int > > :: iterator it;
for(it = Hash[n].begin(); it != Hash[n].end(); it++){
if((*it).first == x){
(*it).second++;
return;
}
}
Hash[n].push_back({x, 1});
}
inline int Find(ui x){
int n = x % MOD;
int ans = 0;
vector < pair < ui, int > > :: iterator it;
for(it = Hash[n].begin(); it != Hash[n].end(); it++){
if((*it).first == x){
ans = (*it).second;
Hash[n].erase(it);
return ans;
}
}
return ans;
}
int main(){
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
string s, a;
cin >> s >> a;
int n = s.size();
int m = a.size();
if(n < m){
cout << 0;
return 0;
}
ui x = 0;
for(int i = 0; i < m; i++){
x = (x + (s[i] - 'a')) * 3;
}
x /= 3;
Insert(x);
ui dif = 1;
for(int i = 1; i < m; i++) dif *= 3;
for(int i = m; i < n; i++){
x = (x - (s[i - m] - 'a') * dif) * 3 + (s[i] - 'a');
Insert(x);
}
int ans = 0;
x = 0;
for(int j = 0; j < m; j++){
x = (x + (a[j] - 'a')) * 3;
}
x /= 3;
ans += Find(x);
while(cin >> a){
x = 0;
for(int j = 0; j < m; j++){
x = (x + (a[j] - 'a')) * 3;
}
x /= 3;
ans += Find(x);
}
cout << ans;
return 0;
}