Pagini recente » Cod sursa (job #471893) | Cod sursa (job #517426) | Cod sursa (job #3210834) | Cod sursa (job #1605746) | Cod sursa (job #105494)
Cod sursa(job #105494)
#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> A[666013], B[65599];
int main(void)
{
FILE *fi = fopen(iname, "r");
char word[22] = {0};
int n;
int m;
int cnt = 0, a, b;
i64 pow3 = 1, 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');
a = t % 666013;
b = t % 65599;
if (A[a].size() < B[b].size())
A[a].push_back(t);
else
B[b].push_back(t);
}
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) {
a = t % 666013;
b = t % 665599;
for (it = A[a].begin(); it != A[a].end(); ++ it) if (*it == t) {
cnt ++;
break ;
}
if (it == A[a].end())
for (it = B[b].begin(); it != B[b].end(); ++ it) if (*it == t) {
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;
}