Pagini recente » Cod sursa (job #2561100) | Cod sursa (job #2333144) | Cod sursa (job #1142773) | Cod sursa (job #2778887) | Cod sursa (job #854601)
Cod sursa(job #854601)
#include <cstdio>
#include <cstring>
#define NMAX 2000005
#define LMAX 4000005
#define HMAX 1005
int n,m,r,C[LMAX],res,sol[HMAX];
char A[LMAX];
void read()
{
fgets(A+1,NMAX,stdin);
n=strlen(A+1)-1;
fgets(A+n+1,NMAX,stdin);
m=strlen(A+n+1)-1;
}
inline int min(int x,int y)
{
return x<y ? x : y;
}
void solve()
{
int i,left,right,pos;
left=right=-1;
for (i=2; i<=n+m; i++)
{
if (right<i)
{
if (A[i]==A[1])
{
left=right=i;
while (right+1<=n+m && A[right+1]==A[right-left+2])
right++;
C[i]=right-left+1;
}
continue ;
}
pos=i-left+1;
if (i+C[pos]-1<right)
{
C[i]=C[pos];
continue ;
}
left=i;
while (right+1<=n+m && A[right+1]==A[right-left+2])
right++;
C[i]=right-left+1;
}
for (i=n+1; i<=n+m; i++)
if (C[i]>=n)
{
res++;
if (res<=1000)
sol[res]=i-n-1;
}
printf("%d\n",res);
for (i=1,res=min(res,1000); i<=res; i++)
printf("%d ",sol[i]);
printf("\n");
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
read();
solve();
return 0;
}