Pagini recente » Clasament a2cos12min2003 | Istoria paginii runda/cerculdeinfo-lectia14-cautare_binara/clasament | Cod sursa (job #1763548) | Cod sursa (job #372495) | Cod sursa (job #2277175)
#include<cstdio>
#include<cstring>
using namespace std;
char a[2000001],b[2000001];
int k[2000001],ap[1001];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s\n",a+1,b+1);
int na=strlen(a+1),nb=strlen(b+1),i,val=0,nr=0;
for(i=2;i<=na;++i)
{
while(val&&a[i]!=a[val+1])
{
val=k[val];
}
if(a[i]==a[val+1])
{
val++;
k[i]=val;
}
else
k[i]=0;
}
val=0;
for(i=1;i<=nb;++i)
{
while(val&&a[val+1]!=b[i])
{
val=k[val];
}
if(b[i]==a[val+1])
val++;
if(val==na)
{
nr++;
if(nr<=1000)
ap[nr]=i-na;
}
}
printf("%d\n",nr);
for(i=1;i<=nr&&i<=1000;++i)
{
printf("%d ",ap[i]);
}
return 0;
}