Pagini recente » Cod sursa (job #2537344) | Cod sursa (job #1439370) | Clasament 28_dec_2017_9 | Cod sursa (job #2834242) | Cod sursa (job #991319)
Cod sursa(job #991319)
# include <cstdio>
# include <cstring>
using namespace std;
int i,pi[2000003],n,m,k,d[2000003],sol,v[100003];
char x[2000003],y[2000003];
void constr_pi()
{
k=0;
pi[1]=0;
for(i=2;i<=n;++i)
{
while(k>0 && x[i]!=x[k+1])
k=pi[k];
if(x[i]==x[k+1])++k;
pi[i]=k;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(x+1);gets(y+1);
n=strlen(x+1);m=strlen(y+1);
constr_pi();k=0;
for(i=1;i<=m;++i)
{
if(k>0 && y[i]!=x[k+1])
k=pi[k];
if(y[i]==x[k+1])++k;
d[i]=k;
if(k==n){++sol;v[sol]=i-n;}
}
printf("%d\n",sol);
for(i=1;i<=sol;++i)
printf("%d ",v[i]);
printf("\n");
return 0;
}