Pagini recente » Cod sursa (job #674840) | Cod sursa (job #1233973) | Cod sursa (job #1258492) | Cod sursa (job #1381747) | Cod sursa (job #1065343)
#include <cstdio>
#include <string.h>
using namespace std;
int i,m,n,d,nr,min,p[2000000],sol[2000000];
char a[2000000],b[2000000];
void prefix(void)
{
p[1]=0;
for (i=2;i<=m;i++)
if (a[i]==a[p[i-1]+1])p[i]=p[i-1]+1;
else p[i]=0;
};
void solve(void)
{
d=1;
i=0;
nr=0;
while (i<=n)
{
i++;
if (a[d]==b[i])if (d==m-1){nr++;sol[nr]=i-m+1;d=p[d]+1;}
else d++;
else while((a[p[d-1]+1]!=b[i])&&(d>1)){d=p[d-1]+1;};
};
printf("%d\n",nr);
if (min>1000)min=1000;
else min=nr;
for (i=1;i<=min;i++)printf("%d ",sol[i]);
};
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",a);
scanf("%s",b);
m= strlen(a);
n=strlen(b);
prefix();
solve();
return 0;
}