Pagini recente » Cod sursa (job #92170) | Cod sursa (job #894506) | Cod sursa (job #2588764) | Cod sursa (job #1482894) | Cod sursa (job #1835368)
#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>
#define TSIZE 10000001
#define WSIZE 21
#define NMAX 33343
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
const int A = 3;
long long int pw[WSIZE];
char text[TSIZE];
struct mapp{
char str[WSIZE];
};
vector <mapp> H[NMAX];
long long int rollh(const char* str)
{
unsigned int length = strlen(str);
long long int hcode = 0;
for (unsigned int i = 0; i < length; i++)
hcode += (str[i] * pw[i]);
return hcode;
}
int hash_f(const char* str)
{
return rollh(str) % NMAX;
}
int _find(const char* str, int key)
{
for (unsigned int i = 0; i < H[key].size(); i++)
if (strcmp(str, H[key][i].str) == 0)
return i;
return -1;
}
int main()
{
mapp aux;
int code, length, length_t, ok = 0;
long long int app = 0;
char word[WSIZE];
///
pw[0] = 1;
for (int i = 1; i < WSIZE; i++)
pw[i] = pw[i - 1] * A;
///
in.getline(text, TSIZE);
while (in.getline(word, WSIZE))
{
code = hash_f(word);
if (!ok)
length = strlen(word), ok = 1;
if (_find(word, code) == -1)
{
strcpy(aux.str, word);
H[code].push_back(aux);
}
}
in.close();
///
for (int i = 0; i < length; i++)
word[i] = text[i];
word[length] = '\0';
///
code = rollh(word);
length_t = strlen(text);
for (int i = length; i < length_t; i++)
{
if (_find(word, code % NMAX) != -1)
app++;
code = (code - text[i - length]) / A + text[i] * pw[length - 1];
///
memmove(word, word + 1, length);
word[length - 1] = text[i];
word[length] = '\0';
}
if (_find(word, code % NMAX) != -1)
app++;
out << app << "\n";
out.close();
return 0;
}