Pagini recente » Cod sursa (job #206508) | Cod sursa (job #1158033) | rosiimici | Cod sursa (job #3208262) | Cod sursa (job #2266740)
#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[0]=0;
l=r=0;
for(i=1;i<=n;i++)
{
if(i<=r)
z[i]=min(z[i-l],r-i+1);
while(i+z[i]<=n&&p[i+z[i]]==p[z[i]])
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);
n=-1;
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;
n++;
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-1);
return 0;
}