Pagini recente » Cod sursa (job #2658806) | Cod sursa (job #136298) | Cod sursa (job #71859) | Cod sursa (job #1643665) | Cod sursa (job #3209592)
#include <bits/stdc++.h>
#define P 43573
#define Q 20113
#define Z 19889
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
int cnt, L, n;
char text[10000005], cuv[25];
unordered_map<int, bool> M;
int main()
{
int i, x1, x2, x3, p1, p2, p3;
fin >> text;
while(fin >> cuv)
{
x1 = x2 = x3 = 0;
for(i = 0;cuv[i] != 0;i++)
{
x1 = (x1 * 3 + cuv[i] - 'a') % P;
x2 = (x2 * 3 + cuv[i] - 'a') % Q;
x3 = (x3 * 3 + cuv[i] - 'a') % Z;
}
M[1LL * x1 * 43573 + x2 + x3] = 1;
}
L = strlen(cuv);
x1 = x2 = x3 = 0;
p1 = p2 = p3 = 1;
for(i = 1;i < L;i++)
{
p1 = p1 * 3 % P;
p2 = p2 * 3 % Q;
p3 = p3 * 3 % Z;
}
for(i = 0;i < L;i++)
{
x1 = (x1 * 3 + text[i] - 'a') % P;
x2 = (x2 * 3 + text[i] - 'a') % Q;
x3 = (x3 * 3 + text[i] - 'a') % Z;
}
if(M[1LL * x1 * 43573 + x2 + x3] == 1)
cnt++;
for(i = L;text[i] != 0;i++)
{
x1 = (x1 - p1 * (text[i - L] - 'a') + P) % P;
x1 = (x1 * 3 + text[i] - 'a') % P;
x2 = (x2 - p2 * (text[i - L] - 'a') + Q) % Q;
x2 = (x2 * 3 + text[i] - 'a') % Q;
x3 = (x3 - p3 * (text[i - L] - 'a') + Z) % Z;
x3 = (x3 * 3 + text[i] - 'a') % Z;
if(M[1LL * x1 * 43573 + x2 + x3] == 1)
cnt++;
}
fout << cnt << "\n";
fout.close();
return 0;
}