Pagini recente » Cod sursa (job #1544363) | Cod sursa (job #285950) | Cod sursa (job #1125949) | Cod sursa (job #593005) | Cod sursa (job #265588)
Cod sursa(job #265588)
//HASHing
#include <fstream>
using namespace std;
typedef long long LL;
const LL BASE = 3;
char text[10000001];
struct nod {
LL val;
nod *next;
};
typedef nod* nodP;
const LL M = 99987;
nodP Hash[100000];
void addHash(LL X) {
LL key = X % M;
nodP nou = new nod;
nou->val = X; nou->next = Hash[key];
Hash[key] = nou;
}
int check(LL X) {
LL key = X % M;
nodP nou = Hash[key];
while (nou != NULL) {
if (nou -> val == X) return 1;
nou = nou->next;
}
return 0;
}
int main() {
ifstream fin("abc2.in");
ofstream fout("abc2.out");
fin >> text;
char word[21];
int m = 0;
while (fin >> word) {
LL idx = 0;
m = 0;
for (int i = 0; word[i]; ++i, ++m) {
idx*=BASE, idx+=(word[i]-'a');
}
addHash(idx);
}
int total = 0;
//adauga
LL number = 0;
LL BB = 1;
for (int i = 1; i < m; ++i) BB*=BASE;
for (int i = 0; i < m; ++i) {
number*=BASE, number+=text[i]-'a';
}
total+=check(number);
for (int i = m; text[i]; ++i) {
number-= (BB * (text[i-m]-'a'));
number*=BASE; number+=text[i] - 'a';
total+=check(number);
}
fout << total << '\n';
return 0;
}