Pagini recente » Cod sursa (job #1920442) | Cod sursa (job #883041) | Cod sursa (job #2551643) | Cod sursa (job #891476) | Cod sursa (job #230397)
Cod sursa(job #230397)
#include<stdio.h>
#include<string.h>
#define NMAX 2000005
#define NMIN 1024
char A1[NMAX],A2[NMAX];
int last[NMAX],sol[NMIN];
int N,M;
long long ANS;
void solve_1()
{
int i,curr=0;
for(i=2; i<=N; ++i)
{
while( curr && A1[i]!=A1[curr+1] ) curr=last[curr];
if( A1[i]==A1[curr+1] ) ++curr;
last[i]=curr;
}
}
void solve_2()
{
int i,curr=0;
for(i=1; i<=M; ++i)
{
while( curr && A2[i]!=A1[curr+1] ) curr=last[curr];
if( A2[i]==A1[curr+1] ) ++curr;
if( curr==N )
{
++ANS;
if( ANS<=1000 )
sol[++sol[0]]=i-curr;
curr=last[curr];
}
}
}
void show()
{
int i;
printf("%lld\n",ANS);
for(i=1; i<=sol[0]; ++i)
printf("%d ",sol[i]);
printf("\n");
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",A1+1);
scanf("%s",A2+1);
N=strlen(A1+1);
M=strlen(A2+1);
solve_1();
solve_2();
show();
return 0;
}