Pagini recente » Cod sursa (job #1267117) | Cod sursa (job #1047993) | Cod sursa (job #1402720) | Cod sursa (job #2556144) | Cod sursa (job #1816045)
#include <cstdio>
#include <cstring>
#define LMax 2000005
#define NMax 1000
#define MIN(a,b)((a)<(b)?(a):(b))
const int P = 147481;
const int Q = 474707;
int rez[NMax+1];
char A[LMax+1];
char B[LMax+1];
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int i,lgA,lgB,a,b,pwrP,pwrQ,u,v,nr;
fgets(A,LMax-1,stdin);
lgA = strlen(A)-1;
fgets(B,LMax-1,stdin);
lgB = strlen(B);
if( B[lgB-1] == '\n' ) --lgB;
if( lgB<lgA ) { printf("0\n"); return 0; }
for(pwrP = pwrQ = i = 1; i < lgA; ++i)
{
pwrP = ( pwrP * 47 ) % P;
pwrQ = ( pwrQ * 47 ) % Q;
}
for(a = b = 0, i = 1; i <= lgA; ++i)
{
a = ( a*47 + A[i-1] ) % P;
b = ( b*47 + A[i-1] ) % Q;
}
for(u = v = nr = 0, i = 1; i <= lgA; ++i)
{
u = ( u*47 + B[i-1] ) % P;
v = ( v*47 + B[i-1] ) % Q;
}
if( u==a&&v==b ) rez[++nr] = 1;
for(i = lgA+1; i <= lgB; ++i)
{
u = ( ( ( u - B[i-lgA-1] * pwrP ) % P + P ) * 47 + B[i-1] ) % P;
v = ( ( ( v - B[i-lgA-1] * pwrQ ) % Q + Q ) * 47 + B[i-1] ) % Q;
if( u==a&&v==b )
{
if(nr<NMax) rez[++nr] = i-lgA;
else ++nr;
}
}
printf("%d\n",nr);
for(i = 1; i <= MIN(NMax,nr); ++i) printf("%d ",rez[i]);
return 0;
}