Pagini recente » Monitorul de evaluare | Diferente pentru utilizator/adriana_s intre reviziile 35 si 34 | Diferente pentru home intre reviziile 115 si 902 | Cod sursa (job #243485) | Cod sursa (job #1291257)
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,i,j,p,q,k,nr,v[2000005],m;
char a[2000005],b[2000005];
int sol[1005];
void prefix()
{
v[1]=0; k=0;
for (i=2;i<=n;i++)
{
while ((k>0)&&(a[i]!=a[k+1])) k=v[k];
if (a[i]==a[k+1]) k++;
v[i]=k;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a+1);
gets(b+1);
n=strlen(a+1);
m=strlen(b+1);
prefix(); k=0;
for (i=1;i<=m;i++)
{
while ((k>0)&&(b[i]!=a[k+1]))
k=v[k];
if (b[i]==a[k+1]) k++;
if (k==n)
{if (sol[0]>=1000)
++sol[0]; else sol[++sol[0]]=i-n;}
}
printf("%d\n",sol[0]);
for (i=1;i<=sol[0];i++) printf("%d ",sol[i]);
return 0;
}