Cod sursa(job #105466)
#include <cstdio>
#include <vector>
using namespace std;
const char iname[] = "abc2.in";
const char oname[] = "abc2.out";
#define MAXN 10000005
typedef long long i64;
char T[MAXN];
vector <i64> V[666013];
bool used[65599] = {true};
int main(void)
{
FILE *fi = fopen(iname, "r");
char word[22] = {0};
int n;
int m;
int cnt = 0, k;
i64 pow3 = 1;
i64 t;
vector <i64>::iterator it;
fscanf(fi, "%s\n", T);
n = (int)strlen(T);
m = 0;
while (fscanf(fi, "%s\n", word) == 1) {
if (m == 0)
m = (int)strlen(word);
t = 0;
for (int i = 0; word[i]; ++ i)
t = t * 3 + (word[i] - 'a');
V[t % 666013].push_back(t);
used[t % 65599] = true;
}
fclose(fi);
for (int i = 1; i < m; ++ i)
pow3 = pow3 * 3;
t = 0;
for (int i = 0; i < m; ++ i)
t = t * 3 + (T[i] - 'a');
for (int i = 0; i <= n - m; ++ i) {
if (used[t % 65599]) {
k = t % 666013;
for (it = V[k].begin(); it != V[k].end(); ++ it)
if (*it == k) {
cnt ++;
break ;
}
}
t = 3 * (t - pow3 * (T[i] - 'a')) + (T[i + m] - 'a');
}
FILE *fo = fopen(oname, "w");
fprintf(fo, "%d\n", cnt);
fclose(fo);
return 0;
}