Pagini recente » Cod sursa (job #2722693) | Cod sursa (job #1825115) | Cod sursa (job #957183) | Cod sursa (job #3251229) | Cod sursa (job #1065349)
#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[0]=0;
for (i=1;i<=m-1;i++)
if (a[i]==a[p[i-1]])p[i]=p[i-1]+1;
else p[i]=0;
};
void solve(void)
{
d=0;
i=-1;
nr=0;
while (i<=n-1)
{
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;
}