Pagini recente » Cod sursa (job #668298) | Cod sursa (job #2166173) | Cod sursa (job #3256493) | Cod sursa (job #1095021) | Cod sursa (job #1378901)
#include <cstdio>
#include <cstring>
using namespace std;
#define lmax 2000002
#define minim(a, b) ((a < b) ? a : b)
char x[lmax],y[lmax];
int pi[lmax],di[lmax],sol[1001];
void prefix()
{
int i,k=0, n=strlen(x)-1;
pi[1]=0;
for (i=2;i<=n;++i)
{
while (k>0 && x[i]!=x[k+1])
k=pi[k];
if (x[i]==x[k+1]) k++;
pi[i]=k;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(x+1, lmax, stdin);
fgets(y+1, lmax, stdin);
x[0] = ' '; y[0] = ' ';
x[strlen(x)-1] = y[strlen(y)-1] = 0;
prefix();
int i,k,m=strlen(y)-1,n=strlen(x)-1,nr=0;
k=0;
for (i=1;i<=m;++i)
{
while (k>0 && y[i]!=x[k+1])
k=pi[k];
if (y[i]==x[k+1]) k++;
di[i]=k;
if (di[i]==n)
{
nr++;
if (nr<=1000) sol[nr]=i-n;
}
}
printf("%d\n",nr);
for (i=1;i<=minim(nr,1000);i++)
printf("%d ",sol[i]);
return 0;
}