Pagini recente » Cod sursa (job #1574796) | Cod sursa (job #299504) | Cod sursa (job #751935) | Cod sursa (job #3122772) | Cod sursa (job #1370347)
#include <cstring>
#include <fstream>
#define N 20000000
#define C 50001
#define MOD 8388593
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
char a[N], c[22];
int la, lc;
unsigned int p[22];
unsigned int h[C], urm[C], lst[MOD], nr = 0;
inline bool cauta(unsigned int x)
{
int r = x % MOD;
for(int i = lst[r]; i; i = urm[i])
if(x == h[i])
return 1;
return 0;
}
inline void adauga(unsigned int x)
{
if(cauta(x))
return;
int r = x % MOD;
h[++nr] = x;
urm[nr] = lst[r];
lst[r] = nr;
}
int main()
{
p[0] = 1;
for(int i = 1; i < 22; i++)
p[i] = p[i - 1] * 3;
in >> a;
la = strlen(a);
while(in >> c)
{
lc = strlen(c);
unsigned int x = 0;
for(int i = 0; i < lc; i++)
x += p[i] * (c[i] - 'a');
adauga(x);
}
int rez = 0;
unsigned int x = 0;
if(lc > la)
{
out << 0 << '\n';
return 0;
}
for(int i = 0; i < lc; i++)
x += p[i] * (a[i] - 'a');
rez += cauta(x);
for(int i = lc; i < la; i++)
{
x /= 3;
x += p[lc - 1] * (a[i] - 'a');
rez += cauta(x);
}
out << rez << '\n';
return 0;
}