Pagini recente » Cod sursa (job #434066) | Cod sursa (job #2831818) | Cod sursa (job #2797515) | Cod sursa (job #941492) | Cod sursa (job #1458071)
#include <cstdio>
#include <cstring>
#define MOD1 666013
#define MOD2 3025129
#define DIM 2000007
#define base 157
using namespace std;
FILE *fin, *fout;
char A[DIM], B[DIM];
int Na, Nb, ha1, ha2, hb1, hb2, occ[DIM], ct, tmp1, tmp2;
int power1(int a, int b)
{
int sol = 1;
for(; b; b>>=1)
{
if(b&1)
{
sol = (1LL*sol*a)%MOD1;
}
a=(1LL*a*a)%MOD1;
}
return sol;
}
int power2(int a, int b)
{
int sol = 1;
for(; b; b>>=1)
{
if(b&1)
{
sol = (1LL*sol*a)%MOD2;
}
a=(1LL*a*a)%MOD2;
}
return sol;
}
void hashA()
{
for(int i = 0; i< Na; i++)
{
ha1 = ((1LL*ha1*base)%MOD1 + (int)A[i])%MOD1;
ha2 = ((1LL*ha2*base)%MOD2 + (int)A[i])%MOD2;
}
}
void hashB()
{
for(int i = 0; i< Na; i++)
{
hb1 = ((1LL*hb1*base)%MOD1 + (int)B[i])%MOD1;
hb2 = ((1LL*hb2*base)%MOD2 + (int)B[i])%MOD2;
}
}
int main()
{
fin = freopen("strmatch.in", "r", stdin);
fout = freopen("strmatch.out", "w", stdout);
scanf("%s", A);
scanf("%s", B);
Na = strlen(A);
Nb = strlen(B);
if(Na > Nb)
{
printf("0\n");
fclose(fin);
fclose(fout);
return 0;
}
hashA();
hashB();
if(ha1 == hb1 && ha2 == hb2)
{
occ[ct] = 0;
ct++;
}
tmp1 = power1(base, Na-1);
tmp2 = power2(base, Na-1);
for(int i = Na; i<= Nb; i++)
{
hb1 = ((hb1 - (1LL*tmp1*B[i-Na])%MOD1 + MOD1)*base + (int)B[i])%MOD1;
hb2 = ((hb2 - (1LL*tmp2*B[i-Na])%MOD2 + MOD2)*base + (int)B[i])%MOD2;
if(ha1 == hb1 && ha2 == hb2)
{
occ[ct] = i-Na+1;
ct++;
}
}
if(ct <= 1000)
{
printf("%d\n", ct);
for(int i = 0; i< ct; i++) printf("%d ", occ[i]);
printf("\n");
}
else
{
printf("%d\n", ct);
for(int i = 0; i< 1000; i++) printf("%d ", occ[i]);
printf("\n");
}
fclose(fin);
fclose(fout);
return 0;
}