Pagini recente » Cod sursa (job #1604603) | Cod sursa (job #2608150) | Cod sursa (job #213989) | Cod sursa (job #2983439) | Cod sursa (job #393703)
Cod sursa(job #393703)
#include<stdio.h>
#include<string.h>
#define Nmx 2000002
char s1[Nmx],s2[Nmx];
int v[Nmx],n,m,sol[Nmx],nr;
void citire()
{
fgets(s1+1,Nmx,stdin);
n=strlen(s1+1)-1;
fgets(s2+1,Nmx,stdin);
m=strlen(s2+1)-1;
}
void solve()
{
int k=0;
v[0]=0;
for(int i=2;i<=n;++i)
{
while(k&&s1[k+1]!=s1[i])
k=v[k];
if(s1[k+1]==s1[i])
++k;
v[i]=k;
}
k=0;
for(int i=1;i<=m;++i)
{
while(k&&s2[i]!=s1[k+1])
k=v[k];
if(s1[k+1]==s2[i])
++k;
if(k==n)
{
k=v[n];
++nr;
if(nr<=1000) sol[nr]=i-n;
}
}
printf("%d\n",nr);
if(nr>1000)
nr=1000;
for(int i=1;i<=nr;++i)
printf("%d ",sol[i]);
printf("\n");
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire();
solve();
return 0;
}