Pagini recente » Cod sursa (job #109820) | Cod sursa (job #2125508) | Cod sursa (job #2498834) | Cod sursa (job #1244185) | Cod sursa (job #3209883)
#include <iostream>
#include <fstream>
#include <unordered_map>
#define N 1000000
#define P 123457
#define Q 666013
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
string s, t;
unordered_map <long long, bool> M;
int n, m;
void Hash()
{
int i, x1, x2;
x1 = x2 = 0;
for (i = 0; i < m; i++)
{
x1 = (x1 * 3 + t[i] - 'a') % P;
x2 = (x2 * 3 + t[i] - 'a') % Q;
}
M[1ll * x1 * N + 1ll * x2] = 1;
}
void Rez()
{
int i, x1, x2, p1, p2, nr_poz;
x1 = x2 = nr_poz = 0;
for (i = 0; i < m; i++)
{
x1 = (x1 * 3 + s[i] - 'a') % P;
x2 = (x2 * 3 + s[i] - 'a') % Q;
}
for (i = p1 = p2 = 1; i < m; i++)
{
p1 = p1 * 3 % P;
p2 = p2 * 3 % Q;
}
nr_poz += M[1ll * x1 * N + 1ll * x2];
for (; i < n; i++)
{
x1 = (x1 - (s[i - m] - 'a') * p1 % P + P) % P;
x2 = (x2 - (s[i - m] - 'a') * p2 % Q + Q) % Q;
x1 = (x1 * 3 + s[i] - 'a') % P;
x2 = (x2 * 3 + s[i] - 'a') % Q;
nr_poz += M[1ll * x1 * N + 1ll * x2];
}
fout << nr_poz << "\n";
}
int main()
{
fin >> s;
n = s.length();
while (fin >> t)
{
m = t.length();
Hash();
}
Rez();
fout.close();
return 0;
}