Pagini recente » Cod sursa (job #1899718) | Cod sursa (job #2233372) | Cod sursa (job #2968317) | Cod sursa (job #1288863) | Cod sursa (job #105539)
Cod sursa(job #105539)
#include <stdio.h>
#include <string.h>
const char iname[] = "abc2.in";
const char oname[] = "abc2.out";
#define MAXN 10000005
char T[MAXN];
struct hash_node {
unsigned int hash;
hash_node * next;
} *H[666013];
inline bool find(int r, unsigned int t)
{
for (hash_node *p = H[r]; p; p = p -> next)
if (p -> hash == t)
return true;
return false;
}
inline void insert(int r, unsigned int t)
{
hash_node *p = new hash_node;
p -> hash = t, p -> next = H[r], H[r] = p;
}
int main(void)
{
FILE *fi = fopen(iname, "r");
char word[22] = {0};
int n;
int m;
int cnt = 0;
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);
unsigned int t = 0;
for (int i = 0; word[i]; ++ i)
t = t * 3 + (word[i] - 'a');
int r = t % 666013;
if (!find(r, t))
insert(r, t);
}
fclose(fi);
unsigned int pow3 = 1;
for (int i = 1; i < m; ++ i)
pow3 = pow3 * 3;
unsigned int t = 0;
for (int i = 0; i < m; ++ i)
t = t * 3 + (T[i] - 'a');
for (int i = 0; i <= n - m; ++ i) {
if (find(t % 666013, t))
cnt ++;
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;
}