Pagini recente » Cod sursa (job #3305220) | Cod sursa (job #2094628) | Cod sursa (job #3358302) | Monitorul de evaluare | Cod sursa (job #1010563)
#include <stdio.h>
#define mini(a,b) ((a<b)?a:b)
#define NMax 2000005
#define fr(i,a,b) for(int i=a;i<=b;++i)
int n,m;
char a[NMax],b[NMax];
int pi[NMax],pos[1024];
void pref()
{
int i, q = 0;
for (i=2,pi[1]=0;i<=m;++i)
{
while(q&&a[q+1]!=a[i])
q=pi[q];
if(a[q+1]==a[i])
++q;
pi[i]=q;
}
}
int main()
{
int i, q = 0, n1 = 0;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,sizeof(a),stdin);
fgets(b,sizeof(b),stdin);
for(;(a[m]>='A'&&a[m]<='Z')||(a[m]>='a'&&a[m]<='z')||(a[m]>='0'&&a[m]<='9');++m);
for(;(b[n]>='A'&&b[n]<='Z')||(b[n]>='a'&&b[n]<='z')||(b[n]>='0'&&b[n]<='9');++n);
for(i=m;i;--i) a[i]=a[i-1];a[0]=' ';
for (i=n;i;--i) b[i]=b[i-1];b[0]=' ';
pref();
fr(i,1,n)
{
while(q&&a[q+1]!=b[i])
q=pi[q];
if (a[q+1]==b[i])
++q;
if (q==m)
{
q=pi[m];
++n1;
if (n1 <= 1000)
pos[n1] = i-m;
}
}
printf("%d\n",n1);
fr(i,1,mini(n1,1000))
printf("%d ",pos[i]);
printf("\n");
return 0;
}