Pagini recente » Cod sursa (job #2158397) | Cod sursa (job #2914543) | Cod sursa (job #231785) | Cod sursa (job #848560) | Cod sursa (job #2901432)
#include <bits/stdc++.h>
#include <unordered_map>
#define mod 666013
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
vector <pair <long long, int>> v[666013];
string text, aux;
long long conversie(string s, long long p)
{
long long nrb3 = 0;
int lg = s.size();
for (int i = 0; i < lg; i++)
nrb3 += (s[i] - 'a') * p, p /= 3;
return nrb3;
}
int main()
{
long long nrb3 = 0;
long long p = 1, p2;
fin >> text;
fin >> aux;
int lg = aux.size();
for (int i = 1; i < lg; i++)
p *= 3;
p2 = p;
for (int i = 0; i < lg; i++)
nrb3 += (text[i]-'a') * p, p /= 3;
v[nrb3 % mod].push_back({ nrb3,1 });
bool ok;
for (int i = 1; i < text.size() - lg + 1; i++)
{
nrb3 = (nrb3 - (text[i - 1] - 'a') * p2) * 3 + (text[i + lg - 1] - 'a');
ok = 0;
for (int j = 0; j < v[nrb3 % mod].size(); j++)
if (v[nrb3 % mod][j].first == nrb3)
{
ok = 1;
v[nrb3 % mod][j].second++;
break;
}
if (ok == 0) v[nrb3 % mod].push_back({ nrb3,1 });
}
long long sol = 0;
long long aux1;
aux1 = conversie(aux, p2);
ok = 0;
for (int j = 0; j < v[aux1 % mod].size(); j++)
if (v[aux1 % mod][j].first == aux1)
{
ok = 1;
sol += v[aux1 % mod][j].second;
v[aux1 % mod][j].first = -1;
break;
}
while (fin >> aux)
{
aux1 = conversie(aux, p2);
for (int j = 0; j < v[aux1 % mod].size(); j++)
if (v[aux1 % mod][j].first == aux1)
{
ok = 1;
sol += v[aux1 % mod][j].second;
v[aux1 % mod][j].first = -1;
break;
}
}
fin.close();
fout<<sol;
fout.close();
return 0;
}