Pagini recente » Cod sursa (job #1565667) | Cod sursa (job #2216200) | Cod sursa (job #664046) | Cod sursa (job #783040) | Cod sursa (job #497424)
Cod sursa(job #497424)
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
#define Nmax 10000010
#define Lmax 22
#define baza 3
#define MOD 131013
unsigned int n, l, sol;
unsigned int pow[Lmax];
char A[Nmax], B[Lmax];
vector <unsigned int> H[MOD + 10];
void add_hash (unsigned int val) {
int p = val % MOD;
for (vector <unsigned int>::iterator it = H[p].begin (); it != H[p].end (); it++)
if (*it == val)
return;
H[p].push_back (val);
}
int find (unsigned int val) {
int p = val % MOD;
for (vector <unsigned int>::iterator it = H[p].begin (); it != H[p].end (); it++)
if (*it == val)
return 1;
return 0;
}
void rezolva () {
unsigned int i, nr = 0;
for (i = 0; i < n; i++) {
if (i >= l) nr-= pow[l-1] * (A[i - l] - 'a');
nr = nr * baza + A[i] - 'a';
if (i >= l - 1) sol+= find (nr);
}
printf ("%u", sol);
}
int main () {
freopen ("abc2.in", "r", stdin);
freopen ("abc2.out", "w", stdout);
unsigned nr, i;
scanf ("%s", A); n = strlen (A);
scanf ("%s", B); l = strlen (B);
pow[0] = 1;
for (i = 1; i <= l; i++)
pow[i] = pow[i-1] * baza;
while (!feof (stdin)) {
nr = 0;
for (i = 0; i < l; i++)
nr+= (pow[l - (i + 1)] * (B[i] - 'a'));
add_hash (nr);
scanf ("%s", B);
}
rezolva ();
return 0;
}