Pagini recente » Cod sursa (job #1342453) | Cod sursa (job #1001940) | Cod sursa (job #2814664) | Cod sursa (job #221380) | Cod sursa (job #547968)
Cod sursa(job #547968)
#include <cstdio>
#include <cstring>
#define MaxN 2000005
#define MaxM 1005
#define infile "strmatch.in"
#define outfile "strmatch.out"
char A[MaxN],B[MaxN];
int pi[MaxN],sol[MaxM],nrsol;
void read()
{
int i,n;
scanf("%s%s",&A,&B);
n=strlen(A);
for(i=n;i>0;i--)
A[i]=A[i-1];
n=strlen(B);
for(i=n;i>0;i--)
B[i]=B[i-1];
A[0]=B[0]='0';
}
void prefix()
{
int n=strlen(A)-1,k=0,i;
for(i=2;i<=n;i++)
{
while(k>0 && A[k+1]!=A[i])
k=pi[k];
if(A[k+1]==A[i])
k++;
pi[i]=k;
}
}
void match()
{
int n=strlen(A)-1,m=strlen(B)-1,k=0,i;
for(i=1;i<=m;i++)
{
while(k>0 && A[k+1]!=B[i])
k=pi[k];
if(A[k+1]==B[i])
k++;
if(k==n)
{
nrsol++;
if(nrsol<=1000)
sol[nrsol]=i-n;
}
}
}
void write()
{
int i;
printf("%d\n",nrsol);
if(nrsol>1000) nrsol=1000;
for(i=1;i<=nrsol;i++)
printf("%d ",sol[i]);
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
prefix();
match();
write();
fclose(stdin);
fclose(stdout);
return 0;
}