Pagini recente » Cod sursa (job #717776) | Cod sursa (job #1970945) | Profil gheorghe.vacari | Cod sursa (job #1767827) | Cod sursa (job #2266727)
#include <bits/stdc++.h>
#include <cstring>
using namespace std;
char a[2000005], b[2000005], p[4000005];
int z[4000005],l,r,i,n,nr,q;
void zet(char p[4000005])
{
// n=strlen(p+1);
z[1]=0;
l=r=0;
for(i=2;i<=n;i++)
{
if(i<=r)
z[i]=min(z[i-l+1],r-i+1);
while(i+z[i]-1<=n&&p[i+z[i]]==p[z[i]+1])
z[i]++;
if(i+z[i]-1>=r)
{
r=i+z[i]-1;
l=i;
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&a);
q=strlen(a);
scanf("%s",&b);
int qq=strlen(b);
// p=strcat(a,"#");
// p=strcat(p,b);
n=0;
for(i=0;i<q;i++)
{
n++;
p[n]=a[i];
}
n++;
p[n]='#';
for(i=0;i<qq;i++)
{
n++;
p[n]=b[i];
}
p[n+1]=0;
zet(p);
for(i=q+1;i<=n;i++)
{
if(z[i]==q)nr++;
}
printf("%d\n",nr);
for(i=q+1;i<=n;i++)
if(z[i]==q)printf("%d ",i-q-2);
return 0;
}