Pagini recente » Cod sursa (job #1377989) | Cod sursa (job #1118900) | Cod sursa (job #2055003) | Cod sursa (job #1630854) | Cod sursa (job #1552531)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char a[2000005],b[2000005];
int n,m,i,k,phi[2000005],poz[2000005],nr,phi2[2000005];
int main()
{
freopen ("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a+1);
gets(b+1);
n=strlen(a+1);
m=strlen(b+1);
phi[1]=0;
for(i=2;i<=n;++i)
{
k=phi[i-1];
while(k>0 && a[i]!=a[k+1])
k=phi[k];
if(a[i]==a[k+1])
phi[i]=k+1;
else phi[i]=0;
}
a[n+1]=' ';
for(i=1;i<=m;++i)
{
k=phi2[i-1];
while(k>0 && b[i]!=a[k+1])
k=phi[k];
if(b[i]==a[k+1])
phi2[i]=k+1;
else phi2[i]=0;
if (phi2[i]==n)
{
nr++;
if(nr<=1000)
poz[nr]=i-n;
}
}
printf("%d\n",nr);
for(i=1;i<=min(nr,1000);i++)
{
printf("%d ",poz[i]);
}
return 0;
}