Pagini recente » Cod sursa (job #1772698) | Cod sursa (job #1728018) | Cod sursa (job #1428866) | Cod sursa (job #430438) | Cod sursa (job #168467)
Cod sursa(job #168467)
#include <fstream>
#include <algorithm>
using namespace std;
const char iname[] = "abc2.in";
const char oname[] = "abc2.out";
#define FOR(i, a, b) for (int i = (a); i < (b); ++ i)
#define MAXN 10000001
char T[MAXN];
struct hash_node {
unsigned int hash_value;
hash_node *next;
} *hash_table[666777];
bool query(int index, unsigned int hash_value) {
for (hash_node *p = hash_table[index]; p; p = p -> next)
if (p -> hash_value == hash_value)
return true;
return false;
}
void insert(int index, unsigned int hash_value) {
hash_node *p = new hash_node;
p -> hash_value = hash_value, p -> next = hash_table[index], hash_table[index] = p;
}
int main(void)
{
ifstream fin(iname);
int n;
int m = 0;
char word[21], *p;
unsigned int h;
int ret = 0;
fin.getline(T, MAXN);
n = (int)strlen(T);
fin.getline(word, 21);
m = (int)strlen(word);
while (*word)
{
h = 0;
for (p = word; *p; ++ p)
h = h * 3 + (*p - 'a');
if (query(h % 666777, h) == false)
insert(h % 666777, h);
fin.getline(word, 21);
}
unsigned int bpm = 1;
FOR (i, 0, m - 1)
bpm *= 3;
h = 0;
FOR (i, 0, m)
h = h * 3 + (T[i] - 'a');
p = T;
FOR (i, 0, n-m+1)
{
if (query(h % 666777, h))
ret ++;
if (i + m < n)
h = (h - bpm * (*p - 'a')) * 3 + (p[m] - 'a');
p ++;
}
ofstream fout(oname);
fout << ret <<'\n';
fin.close(), fout.close();
return 0;
}