Pagini recente » Cod sursa (job #2479997) | Cod sursa (job #2959629) | Cod sursa (job #919921) | Cod sursa (job #409864) | Cod sursa (job #1552487)
#include<cstdio>
#include<cstring>
using namespace std;
int phi[2000003],phi2[2000003],i,n,m,k,nr,poz[1002];
char s1[2000003],s2[2000003];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(s1+1);
gets(s2+1);
m=strlen(s1+1);
for(i=2;i<=m;i++)
{
k=phi[i-1];
while(k>0&&s1[i]!=s1[k+1])
{
k=phi[k];
}
if(s1[i]==s1[k+1])
{
phi[i]=k+1;
}
else
{
phi[i]=0;
}
}
s1[m+1]=' ';
n=strlen(s2+1);
for(i=1;i<=n;i++)
{
k=phi2[i-1];
while(k>0&&s2[i]!=s1[k+1])
{
k=phi[k];
}
if(s2[i]==s1[k+1])
{
phi2[i]=k+1;
}
else
{
phi2[i]=0;
}
if(phi2[i]==m)
{
nr++;
if(nr<=1000)
{
poz[nr]=i-m;
}
}
}
printf("%d\n",nr);
for(i=1;i<=nr;i++)
{
printf("%d ",poz[i]);
}
}