Pagini recente » Cod sursa (job #357524) | Cod sursa (job #476431) | Cod sursa (job #89813) | Cod sursa (job #2097994) | Cod sursa (job #425568)
Cod sursa(job #425568)
#include <cstdio>
#include <cstring>
char a[2000050],b[2000050];
int pia[2000050],pib[2000050];
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;
}
}
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=pib[i-1]-1;
if (a[pib[i-1]]==b[i])
{
pib[i]=pib[i-1]+1;
continue;
}
while (y&&!k)
{
if (a[y]==b[i])
{
pib[i]=y+1;
k=1;
}
y=pia[y];
}
}
int n=strlen(a),cnt=0;
for (i=0;b[i];++i)
if (pib[i]==n)
++cnt;
printf("%d\n",cnt);
for (i=0;b[i];++i)
if (pib[i]==n)
printf("%d ",i-n+1);
printf("\n");
return 0;
}