Pagini recente » Cod sursa (job #2543496) | Cod sursa (job #881811) | Cod sursa (job #501602) | Cod sursa (job #1699017) | Cod sursa (job #1458215)
#include <cstdio>
#include <cstring>
#define MOD1 100021
#define MOD2 100007
#define DIM 2000007
#define base 73
using namespace std;
FILE *fin, *fout;
char A[DIM], B[DIM];
int Na, Nb, ha1, ha2, hb1, hb2, occ[DIM], ct, p1=1, p2=1;
void hashA()
{
for(int i = 0; i< Na; i++)
{
ha1 = ((1LL*ha1*base)%MOD1 + A[i])%MOD1;
ha2 = ((1LL*ha2*base)%MOD2 + A[i])%MOD2;
if(i)
{
p1 = (p1*base)%MOD1;
p2 = (p2*base)%MOD2;
}
}
}
void hashB()
{
for(int i = 0; i< Na; i++)
{
hb1 = ((1LL*hb1*base)%MOD1 + B[i])%MOD1;
hb2 = ((1LL*hb2*base)%MOD2 + 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*p1*B[i-Na])%MOD1 + MOD1)*base + B[i])%MOD1;
hb2 = ((hb2 - (1LL*p2*B[i-Na])%MOD2 + MOD2)*base + 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;
}