Pagini recente » Cod sursa (job #2658821) | Cod sursa (job #1766140) | Cod sursa (job #2170275) | Cod sursa (job #3138786) | Cod sursa (job #1712373)
//z algoritm
#include <stdio.h>
#include <string.h>
char s[4000009];
int z[4000009],n,m,p[1025],k,i;
void z_f(char *s,int * z,int n)
{
int r=0,l=0,i,k;
for (i=1;i<n;++i)
{
if (i>r)
{
l=i;
r=i;
while (r<n && s[r-l]==s[r])
r++;
r--;
z[i]=r-l+1;
} else
{
if (z[i-l]<r-i+1)
z[i]=z[i-l]; else
{
l=i;
while (r<n && s[r-l]==s[r])
r++;
r--;
z[i]=r-l+1;
}
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",s);
n=strlen(s);
s[n]='#';
scanf("%s",s+n+1);
m=strlen(s)-n-1;
//printf("%s \n",s);
z_f(s,z,n+m+1);
for (i=n+1;i<=n+m+1;++i)
if (z[i]==n)
{
if (k<1000)
p[k]=i;
k++;
}
printf("%d\n",k);
for (i=0;i<(k<1000 ? k : 1000);++i)
printf("%d ",p[i]-n-1);
return 0;
}