Pagini recente » Cod sursa (job #2416837) | Cod sursa (job #2138120) | Cod sursa (job #986552) | Cod sursa (job #3172373) | Cod sursa (job #159783)
Cod sursa(job #159783)
#include<stdio.h>
#include<string.h>
#define Nm (1<<21)
#define Km 1000
char A[Nm],B[Nm];
int Pi[Nm],Ans[Km+1],ans,k;
void read()
{
freopen("strmatch.in","r",stdin);
gets(A+1);
gets(B);
}
void solve()
{
int i,p,n=strlen(A+1);
Pi[1]=p=0;
for(i=2;i<=n;++i)
{
while(p && A[p+1]!=A[i])
p=Pi[p];
if(A[p+1]==A[i])
++p;
Pi[i]=p;
}
for(p=i=0;B[i];++i)
{
while(p && A[p+1]!=B[i])
p=Pi[p];
if(A[p+1]==B[i])
++p;
if(p==n)
{
++ans;
p=Pi[p];
if(k<Km)
Ans[++k]=i-n+1;
}
}
}
void write()
{
int i;
freopen("strmatch.out","w",stdout);
printf("%d\n",ans);
if(!k)
return;
for(i=1;i<k;++i)
printf("%d ",Ans[i]);
printf("%d\n",Ans[i]);
}
int main()
{
read();
solve();
write();
return 0;
}