Pagini recente » Istoria paginii runda/s | Cod sursa (job #2481237) | Cod sursa (job #2554718) | Cod sursa (job #1669635) | Cod sursa (job #1761477)
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int NMax = 5005;
const int MOD = 100007;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
vector < pair < ll, int > > Hash[MOD];
inline void Insert(ll x){
int n = x % MOD;
for(int i = 0; i < Hash[n].size(); i++){
if(Hash[n][i].first == x){
Hash[n][i].second++;
return;
}
}
Hash[n].push_back({x, 1});
}
inline int Find(ll x){
int n = x % MOD;
int ans = 0;
for(int i = 0; i < Hash[n].size(); i++){
if(Hash[n][i].first == x){
ans = Hash[n][i].second;
Hash[n][i].second = 0;
return ans;
}
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
fin.tie(NULL);
string s, a;
fin >> s >> a;
int n = s.size();
int m = a.size();
if(n < m){
cout << 0;
return 0;
}
ll x = 0;
for(int i = 0; i < m; i++){
x = (x + (s[i] - 'a')) * 3;
}
x /= 3;
Insert(x);
ll 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(fin >> a){
x = 0;
for(int j = 0; j < m; j++){
x = (x + (a[j] - 'a')) * 3;
}
x /= 3;
ans += Find(x);
}
fout << ans;
return 0;
}