Pagini recente » Cod sursa (job #1908576) | Cod sursa (job #2544485) | Cod sursa (job #2353596) | Cod sursa (job #1527787) | Cod sursa (job #3209885)
#include <iostream>
#include <fstream>
#include <set>
#define N 1000000
#define P 123457
#define Q 666013
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
string s, t;
set <long long> S;
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;
}
S.insert(1LL * x1 * N + 1LL * x2);
}
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;
}
if (S.find(1LL * x1 * N + 1LL * x2) != S.end())
nr_poz++;
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;
if (S.find(1LL * x1 * N + 1LL * x2) != S.end())
nr_poz++;
}
fout << nr_poz << "\n";
}
int main()
{
fin >> s;
n = s.length();
while (fin >> t)
{
m = t.length();
Hash();
}
Rez();
fout.close();
return 0;
}