Pagini recente » Cod sursa (job #1020676) | Cod sursa (job #1821122) | Cod sursa (job #1123270) | Cod sursa (job #3238562) | Cod sursa (job #919562)
Cod sursa(job #919562)
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
#include <vector>
#define MOD 666013
using namespace std;
int n, m;
int sol;
char a[10000010];
vector <unsigned int> H[666013];
inline void Read()
{
ifstream f ("abc2.in");
f>>(a+1);
n = strlen(a+1);
char ch[25];
unsigned int nr, put = 1;
int i;
f>>(ch+1);
m = strlen(ch+1);
nr = 0;
for (i=1; i<=m; i++)
nr = nr*3 + (ch[i] - 'a');
H[nr%MOD].push_back(nr);
while (f>>(ch+1))
{
nr = 0;
for (i=1; i<=m; i++)
nr = nr*3 + (ch[i] - 'a');
H[nr%MOD].push_back(nr);
}
f.close();
}
inline void Solve()
{
if (n<m)
{
ofstream g("abc2.out");
g<<"0\n";
g.close();
return ;
}
unsigned int nr, put = 1, poz;
bool gasit;
vector <unsigned int>::iterator it, final;
int i;
// put = 3^(m-1);
for (i=1; i<m; i++)
put = put*3;
nr = 0;
for (i=1; i<=m; i++)
nr = nr*3 + (a[i] - 'a');
poz = nr%MOD;
for (gasit = false, it = H[poz].begin(), final = H[poz].end(); it!=final && !gasit; it++)
if (*it == nr)
gasit = true;
sol+=gasit;
for (; i<=n; i++)
{
nr = (nr - put*(a[i-m]-'a'))*3 + (a[i] - 'a');
poz = nr%MOD;
for (it = H[poz].begin(), final = H[poz].end(); it!=final; it++)
if (*it == nr)
sol++, it = final - 1;
}
ofstream g("abc2.out");
g<<sol<<"\n";
g.close();
}
int main()
{
Read();
Solve();
return 0;
}