Pagini recente » Istoria paginii utilizator/sygandreiionita | Cod sursa (job #1837898) | Cod sursa (job #608719) | Istoria paginii runda/simulare23.10 | Cod sursa (job #425635)
Cod sursa(job #425635)
#include <cstdio>
#include <cstring>
char a[2000050],b[2000050];
int pia[2000050],pib[2000050];
int cnt;
int main()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
gets(a);
gets(b);
int i;
for (i=1;a[i];++i)
{
if (a[i]==a[0])
pia[i]=1;
int y=i-1;
while (y+1)
{
if (a[pia[y]]==a[i]&&pia[y]+1>pia[i])
pia[i]=pia[y]+1;
y=pia[y]-1;
}
}
int n=i;
if (b[0]==a[0])
pib[0]=1;
bool k;
for (i=1;b[i];++i)
{
k=0;
if (b[i]==a[0])
pib[i]=1;
int y=pia[pib[i-1]-1];
if (a[pib[i-1]]==b[i])
{
pib[i]=pib[i-1]+1;
if (pib[i]==n)
++cnt;
continue;
}
while (y&&!k)
{
if (a[y]==b[i])
{
pib[i]=y+1;
k=1;
}
y=pia[y-1];
}
}
printf("%d\n",cnt);
cnt=0;
for (i=0;b[i];++i)
if (pib[i]==n)
{
if (cnt==1000)
break;
printf("%d ",i-n+1);
++cnt;
}
printf("\n");
return 0;
}