Pagini recente » Cod sursa (job #889005) | Cod sursa (job #2768234) | Cod sursa (job #121323) | Cod sursa (job #745212) | Cod sursa (job #1144558)
#include <cstdio>
#include <cstring>
#define N 2000010
using namespace std;
char P[N],T[N];
int LP,LT,nr,i,k,pr[N],S[1005];
void prefix(),kmp();
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",P+1,T+1);
LP=strlen(P+1);
LT=strlen(T+1);
prefix();
kmp();
printf("%d\n",nr);
nr=nr>1000?1000:nr;
for(i=1;i<=nr;i++)
printf("%d ",S[i]);
return 0;
}
void prefix()
{
//se calculeaza functia prefix pentru patern P
//pr[i]=cel mai lung sufix al prefixului P[1]P[2]....P[i] care este prefix propriu in P
k=0;
for(i=2;i<=LP;i++)
{
while(k&&P[i]!=P[k+1])k=pr[k];
if(P[i]==P[k+1])k++;
pr[i]=k;
}
}
void kmp()
{
k=0;
for(i=1;i<=LT;i++)
{
while(k&&T[i]!=P[k+1])k=pr[k];
if(T[i]==P[k+1])k++;
if(k==LP)
{
nr++;
if(nr<=1000)S[nr]=i-LP;
}
}
}