Pagini recente » Cod sursa (job #1405927) | Cod sursa (job #554595) | Cod sursa (job #2946671) | Cod sursa (job #1815398) | Cod sursa (job #2266739)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[2000010],p[4000010];
int z[4000010],ap[1001];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(p);
int np=strlen(p),nrap=0;
gets(s);
p[strlen(p)]='#';
strcat(p,s);
int n=strlen(p);
int l=0,r=0,i;
for(i=1;i<n;++i)
{
if(i<=r)
z[i]=min(z[i-l],r-i+1);
while(i+z[i]<n&&p[i+z[i]]==p[z[i]])
{
z[i]++;
}
if(i+z[i]-1>=r)
{
r=i+z[i]-1;
l=i;
}
if(z[i]==np)
{
nrap++;
if(nrap<=1000)
ap[nrap]=i-np-1;
}
}
printf("%d\n",nrap);
for(i=1;i<=nrap&&i<=1000;++i)
{
printf("%d ",ap[i]);
}
return 0;
}