Pagini recente » Cod sursa (job #1206751) | Cod sursa (job #2072851) | Cod sursa (job #2400743) | Cod sursa (job #2895850) | Cod sursa (job #432238)
Cod sursa(job #432238)
#include <cstdio>
#include <cstring>
char a[2000010],b[2000010];
int n,m,cnt,pia[2000010],pib[2000010];
void citire()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
gets(a);
gets(b);
n=strlen(a);
m=strlen(b);
for (int i=n;i;--i)
a[i]=a[i-1];
a[0]='$';
for (int i=m;i;--i)
b[i]=b[i-1];
b[0]='$';
}
int main()
{
citire();
int i;
for (i=2;a[i];++i)
{
int y=pia[i-1];
while (a[y+1]!=a[i]&&y)
y=pia[y];
if (a[y+1]==a[i])
pia[i]=y+1;
}
for (int i=1;b[i];++i)
{
int y=pib[i-1];
while (a[y+1]!=b[i]&&y)
y=pia[y];
if (a[y+1]==b[i])
pib[i]=y+1;
if (pib[i]==n)
++cnt;
}
printf("%d\n",cnt);
cnt=0;
for (int i=1;i<=m;++i)
if (pib[i]==n)
if (cnt==1000)
break;
else
{
printf("%d ",i-n);
++cnt;
}
return 0;
}