Pagini recente » Cod sursa (job #486504) | Cod sursa (job #745038) | Cod sursa (job #2810146) | Cod sursa (job #137964) | Cod sursa (job #2039698)
#include <cstdio>
#include <cstring>
using namespace std;
char w[2000005],s[2000005];
int t[2000005];
int sol[2000005],soll=0;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int lw,ls;
scanf("%s",w+1);
scanf("%s",s+1);
t[0]=-1;
t[1]=0;
lw=strlen(w+1);
for(int i=2;i<=lw;++i)
{
int k=i-1;
while(t[k]!=-1&&w[t[k]+1]!=w[i])
k=t[k];
t[i]=t[k]+1;
}
ls=strlen(s+1);
int wi=1;
int si=0;
while(si+wi<=ls)
{
if(w[wi]==s[si+wi])
{
wi++;
if(wi==lw+1)
{
wi--;
++soll;
sol[soll]=si;
si=si+wi-t[wi];
wi=t[wi]+1;
}
}
else
{
if(t[wi]>0)
{
si=si+wi-t[wi];
wi=t[wi]+1;
}
else
{
si=si+wi;
wi=1;
}
}
}
printf("%d\n",soll);
if(soll>=1000)
soll=1000;
for(int i=1;i<=soll;++i)
printf("%d ",sol[i]);
return 0;
}