Pagini recente » Cod sursa (job #1482568) | Cod sursa (job #2059090) | Cod sursa (job #1374003) | Cod sursa (job #1589762) | Cod sursa (job #1482457)
#include <bits/stdc++.h>
#define Q 17
#define P 123457
#define R 300007
using namespace std;
vector <int> h[P+3];
char text[10000004];
int e[23], f[23];
void Init()
{
int i;
e[0] = f[0] = 1;
for (i = 1; i <= 21; i++)
{
e[i] = (e[i - 1] * Q) % P;
f[i] = (f[i - 1] * Q) % R;
}
}
inline void Adauga(int x, int val)
{
h[x].push_back(val);
}
inline int Cauta(int x, int val)
{
for (unsigned i = 0; i < h[x].size(); i++)
if (h[x][i] == val) return i;
return -1;
}
void Sterge(int r, int y)
{
int i, L;
L = h[r].size();
i = Cauta(r, y);
if (i != -1)
{
h[r][i] = h[r][L-1];
h[r].pop_back();
}
}
int main()
{
int x, y, i, j, L, PQ, RQ, cnt;
string s;
Init();
ifstream fin("abc2.in");
ofstream fout("abc2.out");
fin >> text;
/// creare hash
while (fin >> s)
{
x = y = 0;
L = s.length();
for (i = 0; i < L; i++)
{
j = s[i] - 'a';
x = (x * Q + j) % P;
y = (y * Q + j) % R;
}
i = Cauta(x, y);
if (i == -1) Adauga(x, y);
}
PQ = e[L - 1];
RQ = f[L - 1];
///creare primul numar
x = y = 0;
for (i = 0; i < L; i++)
{
j = text[i] - 'a';
x = (x * Q + j) % P;
y = (y * Q + j) % R;
}
cnt = 0;
i = Cauta(x, y);
if (i > -1)
cnt++;
for (i = L; text[i]; i++)
{
///hash1 = ((hash1-(B[i-NA]*P1)%MOD1 + MOD1) * P + B[i]) % MOD1;
x = ((x-((text[i-L] - 'a') * PQ) % P + P)*Q + (text[i]-'a')) % P;
y = ((y-((text[i-L] - 'a') * RQ) % R + R)*Q + (text[i]-'a')) % R;
j = Cauta(x, y);
if (j > -1)
cnt++;
}
fout << cnt << "\n";
fin.close();
fout.close();
return 0;
}