Pagini recente » Cod sursa (job #638034) | Cod sursa (job #2197372) | Cod sursa (job #2869401) | Cod sursa (job #2078269) | Cod sursa (job #168451)
Cod sursa(job #168451)
#include <fstream>
#include <set>
#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];
set <unsigned int> hash[666777u];
int main(void)
{
ifstream fin(iname);
int n;
int m = 0;
char word[21];
unsigned int h, h2;
int ret = 0;
fin.getline(T, MAXN);
n = (int)strlen(T);
fin.getline(word, 21);
m = (int)strlen(word);
while (*word)
{
h = 0;
for (char *p = word; *p; ++ p)
h = h * 3 + (*p - 'a');
hash[h % 666777u].insert(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');
FOR (i, 0, n-m+1)
{
h2 = h % 666777u;
if (hash[h2].find(h) != hash[h2].end())
ret ++;
if (i + m < n)
h = (h - bpm * (T[i] - 'a')) * 3 + (T[i + m] - 'a');
}
ofstream fout(oname);
fout << ret <<'\n';
fin.close(), fout.close();
return 0;
}