Pagini recente » Cod sursa (job #2031503) | Cod sursa (job #1830896) | Cod sursa (job #32238) | Cod sursa (job #2487664) | Cod sursa (job #1552507)
#include <bits/stdc++.h>
using namespace std;
int n,i,k,phi[2000010],p[1010],phii[2000010],m,nr;
char a[2000010],b[2000010];
int main()
{
freopen("strmach.in","r",stdin);
ofstream g ("strmach.out");
gets(a+1);
gets(b+1);
phi[1]=0;
m=strlen(a+1);
for(i=2; i<=m; ++i)
{
k=phi[i-1];
while(k>0&&a[i]!=a[k+1])k=phi[k];
if(a[i]==a[k+1])phi[i]=k+1;
else phi[i]=0;
}
a[m+1]='!';
n=strlen(b+1);
for(i=1; i<=n; ++i)
{
k=phii[i-1];
while(b[i]!=a[k+1]&&k)k=phi[k];
if(b[i]==a[k+1])phii[i]=k+1;
else phii[i]=0;
if(phii[i]==m)
{
++nr;
if(nr<=1000)p[nr]=i-m;
}
}
g<<nr<<'\n';
for(i=1; i<=min(nr,1000); ++i)
g<<p[i]<<" ";
return 0;
}