Pagini recente » Cod sursa (job #508458) | Cod sursa (job #2756290) | Cod sursa (job #2825272) | Cod sursa (job #2983632) | Cod sursa (job #565449)
Cod sursa(job #565449)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define MAXN 10000010
#define MAXW 21
#define MOD1 666013
#define MOD2 666019
#define SIGMA 24
FILE* fin = fopen ("abc2.in", "r");
FILE* fout = fopen ("abc2.out", "w");
vector<int> hash [MOD1];
char buf[MAXN], str[MAXW];
int len, n;
typedef vector <int>::iterator iter;
inline void add (int key1, int key2)
{
for (iter it = hash[key1].begin (); it != hash[key1].end (); ++it) {
if (*it == key2) {
return;
}
}
hash[key1].push_back (key2);
}
inline bool getHash (int key1, int key2)
{
for (iter it = hash[key1].begin (); it != hash[key1].end (); ++it) {
if (*it == key2) {
return true;
}
}
return false;
}
inline void process ()
{
int key1 = 0, key2 = 0;
for (int i = 0; i < len; ++i) {
key1 = (key1 * SIGMA + str[i]) % MOD1;
key2 = (key2 * SIGMA + str[i]) % MOD2;
}
add (key1, key2);
}
int main ()
{
fgets (buf, MAXN, fin);
fgets (str, MAXW, fin);
len = strlen (str) - 1;
n = strlen (buf) - 1;
process ();
while (!feof (fin) && fgets (str, MAXW, fin)) {
process ();
}
int h1 = 1, h2 = 1, p1 = 0, p2 = 0;
for (int i = 0; i < len; ++i) {
p1 = (SIGMA * p1 + buf[i]) % MOD1;
p2 = (SIGMA * p2 + buf[i]) % MOD2;
if (i != 0) {
h1 = (h1 * SIGMA) % MOD1;
h2 = (h2 * SIGMA) % MOD2;
}
}
int match = 0;
for (int i = 0; i <= n - len; ++i) {
match += getHash (p1, p2);
if (i < n - len) {
p1 = ((p1 - (buf[i] * h1) % MOD1 + MOD1) * SIGMA + buf[i + len]) % MOD1;
p2 = ((p2 - (buf[i] * h2) % MOD2 + MOD2) * SIGMA + buf[i + len]) % MOD2;
}
}
fprintf (fout, "%d\n", match);
fclose (fin);
fclose (fout);
return 0;
}