Pagini recente » Monitorul de evaluare | Cod sursa (job #1773263) | Cod sursa (job #305540) | Cod sursa (job #1523566) | Cod sursa (job #2299033)
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
const int LMAX = 10000005;
const int NMAX = 50005;
const int MOD = 10041;
char s[LMAX];
char a[NMAX][25];
vector <int> vec[MOD];
int p3[25];
int main() {
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
scanf("%s", s);
int m = (int)strlen(s);
int top = 1;
for( ; scanf("%s", a[top]) != EOF; top++);
top--;
int n = (int)strlen(a[1]);
for(int i = 1; i <= top; i++) {
unsigned int nr = 0;
for(int j = 0; j < n; j++) {
nr = nr * 3 + (a[i][j] - 'a');
}
bool ok = 0;
int mm = nr % MOD;
for(int it = 0; ok == 0 && it < vec[mm].size(); it++) {
if(vec[mm][it] == nr) {
ok = 1;
}
}
if(ok == 0) {
vec[mm].push_back(nr);
}
}
unsigned int nr3 = 1;
for(int i = 0; i <= 21; i++) {
p3[i] = nr3;
nr3 = nr3 * 3;
}
if(m < n) {
printf("0\n");
return 0;
}
unsigned int nr = 0;
for(int i = 0; i < n; i++) {
nr = nr * 3 + (s[i] - 'a');
}
unsigned int sol = 0;
int mm = nr % MOD;
for(int it = 0; it < vec[mm].size(); it++) {
if(vec[mm][it] == nr) {
sol++;
it = (int)vec[mm].size();
}
}
for(int i = n; i < m; i++) {
nr = nr - (s[i - n] - 'a') * p3[n - 1];
nr = nr * 3 + (s[i] - 'a');
int mm = nr % MOD;
for(int it = 0; it < vec[mm].size(); it++) {
if(vec[mm][it] == nr) {
sol++;
it = (int)vec[mm].size();
}
}
}
printf("%d\n", sol);
return 0;
}