Pagini recente » Cod sursa (job #2187316) | Cod sursa (job #151303) | Cod sursa (job #1808343) | Cod sursa (job #10167) | Cod sursa (job #360869)
Cod sursa(job #360869)
#include<stdio.h>
#include<string.h>
#define N 2000010
int LA,LB,NP,PO[N],PA[N];
char A[N],B[N],*C;
void read(),solve(),prefix(),potriviri();
int main()
{
read();
solve();
return 0;
}
void read()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
C=A;*C='#';C++;scanf("%s",C);LA=strlen(C);
C=B;*C='#';C++;scanf("%s",C);LB=strlen(C);
}
void solve()
{
prefix();
potriviri();
}
void prefix()
{
//se defineste functia prefix pentru surul A
//adica pentru sirul cautat ca subsir
for(int i=2,q=0;i<=LA;i++)
{
while(q&A[q+1]!=A[i])q=PA[q];
if(A[q+1]==A[i])q++;
PA[i]=q;
}
}
void potriviri()
{
for(int i=1,q=0;i<=LB;i++)
{
while(q&&A[q+1]!=B[i])q=PA[q];
if(A[q+1]==B[i])q++;
if(q==LA){q=PA[LA];PO[++NP]=i-LA;}
}
printf("%d\n",NP);
NP=NP<=1000?NP:1000;
for(int i=1;i<=NP;i++)printf("%d ",PO[i]);
printf("\n");
}