Pagini recente » Cod sursa (job #2414978) | Cod sursa (job #129883) | Cod sursa (job #2790949) | Cod sursa (job #277773) | Cod sursa (job #1520172)
#include <fstream>
#include <string.h>
#define MOD1 100007
#define MOD2 100021
#define BAZA 73
#define N_MAX 2000002
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[N_MAX];
char b[N_MAX];
int aHash1, aHash2;
int bHash1, bHash2;
int pow1, pow2;
int sol[N_MAX];
int k;
int main()
{
int len1, len2;
int i;
f >> a;
f.get();
f >> b;
len1 = strlen(a);
len2 = strlen(b);
if (len1 > len2){
g << 0 << '\n';
return 0;
}
pow1 = pow2 = 1;
aHash1 = aHash2 = 0;
k = 0;
for (i = 0; i < len1; ++i){
aHash1 = (aHash1 * BAZA + a[i])%MOD1;
aHash2 = (aHash2 * BAZA + a[i])%MOD2;
if (i != 0){
pow1 = (pow1 * BAZA)%MOD1;
pow2 = (pow2 * BAZA)%MOD2;
}
}
bHash1 = bHash2 = 0;
for (i = 0; i < len1; ++i){
bHash1 = (bHash1 * BAZA + b[i])%MOD1;
bHash2 = (bHash2 * BAZA + b[i])%MOD2;
}
if (aHash1 == bHash1 && aHash2 == bHash2){
sol[k++] = 0;
}
for (i = len1; i < len2; ++i){
bHash1 = ((bHash1 - (b[i - len1] * pow1)%MOD1 + MOD1) * BAZA + b[i])%MOD1;
bHash2 = ((bHash2 - (b[i - len1] * pow2)%MOD2 + MOD2) * BAZA + b[i])%MOD2;
if (aHash1 == bHash1 && aHash2 == bHash2){
sol[k++] = i - len1 + 1;
}
}
g << k << '\n';
for (i = 0; i < k; ++i){
g << sol[i] << ' ';
}
g << '\n';
f.close();
g.close();
return 0;
}