Pagini recente » Cod sursa (job #3287870) | Cod sursa (job #1147156) | Cod sursa (job #125461) | Cod sursa (job #1158149) | Cod sursa (job #612831)
Cod sursa(job #612831)
#include <iostream>
#include <stdlib.h>
#include <fstream>
using namespace std;
const int _MAX_LENGTH_ = 2000001;
const int NR_PRIM_1 = 13;
const int NR_PRIM_2 = 13; //17;
const int NR_HASH_1 = 100007;//666203;
const int NR_HASH_2 = 100021;//1000001;
char a[_MAX_LENGTH_];
char b[_MAX_LENGTH_];
void read();
void solve();
void check();
void print();
int main()
{
read();
solve();
check();
print();
return 0;
}
void read()
{
ifstream ifs("strmatch.in", fstream::in);
ifs >> a >> b;
};
int nr_sol;
int sol[10000];
void solve()
{
freopen("strmatch.out", "w", stdout);
int p1 = 1;
int p2 = 1;
int a_hash_1 = 0;
int a_hash_2 = 0;
int b_hash_1 = 0;
int b_hash_2 = 0;
int i, j;
int strlen_a = 0;
int strlen_b = 0;
for (strlen_a = 0; a[strlen_a] != 0; ++strlen_a);
for (strlen_b = 0; b[strlen_b] != 0; ++strlen_b);
if (strlen_a > strlen_b) printf("0\n");
for (int i = 0; i < strlen_a; ++i)
{
a_hash_1 = ((a_hash_1 * NR_PRIM_1) % NR_HASH_1 + a[i]) % NR_HASH_1;
a_hash_2 = ((a_hash_2 * NR_PRIM_2) % NR_HASH_2 + a[i]) % NR_HASH_2;
b_hash_1 = ((b_hash_1 * NR_PRIM_1) % NR_HASH_1 + b[i]) % NR_HASH_1;
b_hash_2 = ((b_hash_2 * NR_PRIM_2) % NR_HASH_2 + b[i]) % NR_HASH_2;
if (i == 0) continue;
p1 = (p1 * NR_PRIM_1)% NR_HASH_1;
p2 = (p2 * NR_PRIM_2)% NR_HASH_2;
}
if (a_hash_1 == b_hash_1 && a_hash_2 == b_hash_2)
sol[++nr_sol] = 0;
for (j = strlen_a; j < strlen_b; ++j)
{
b_hash_1 = b_hash_1 - (b[j-strlen_a] * p1) % NR_HASH_1 + NR_HASH_1;
b_hash_2 = b_hash_2 - (b[j-strlen_a] * p2) % NR_HASH_2 + NR_HASH_2;
b_hash_1 = b_hash_1 % NR_HASH_1;
b_hash_2 = b_hash_2 % NR_HASH_2;
b_hash_1 = ((b_hash_1 * NR_PRIM_1) % NR_HASH_1 + b[j]) % NR_HASH_1;
b_hash_2 = ((b_hash_2 * NR_PRIM_2) % NR_HASH_2 + b[j]) % NR_HASH_2;
if (a_hash_1 == b_hash_1 && a_hash_2 == b_hash_2)
sol[++nr_sol] = j + 1 -strlen_a;
}
printf("%d\n", nr_sol);
for (int i = 1; i <= 1000; ++i)
printf("%d ", sol[i]);
};
void check()
{
};
void print()
{
//ofstream ofs("strmatch.out", fstream::out);
//ofs << a << "\n" << b << "\n";
};