Pagini recente » Borderou de evaluare (job #1004059) | Borderou de evaluare (job #2877881) | Cod sursa (job #428277) | Cod sursa (job #576305) | Cod sursa (job #896096)
Cod sursa(job #896096)
#include <cstdio>
#define minim(a, b) ((a < b) ? a : b)
#define MAXN 2000005
int n,m,pi[MAXN],pos[1024];
char a[MAXN],b[MAXN];
void prefix()
{
pi[1]=0;
int k=0,i;
for(i=2;i<=n;i++)
{
while(k>0 && a[k+1]!=a[i])
k=pi[k];
if(a[k+1]==a[i])
k++;
pi[i]=k;
}
}
int kmp()
{
int i,k=0,nr=0;
for(i=1;i<=m;i++)
{
while(k>0 && a[k+1]!=b[i])
k=pi[k];
if(a[k+1]==b[i])
k++;
if(k==n)
{
k=pi[n];
nr++;
if(nr<=1000)
pos[nr]=i-n;
}
}
return nr;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a,sizeof(a),stdin);
fgets(b,sizeof(b),stdin);
for(;(a[n]>='A' && a[n]<='Z') || (a[n]>='a' && a[n]<='z') || (a[n]>='0' && a[n]<='9');n++);
for(;(b[m]>='A' && b[m]<='Z') || (b[m]>='a' && b[m]<='z') || (b[m]>='0' && b[m]<='9');m++);
int i;
for(i=n;i;i--)
a[i]=a[i-1];
for(i=m;i;i--)
b[i]=b[i-1];
a[0]=' ';
b[0]=' ';
prefix();
int nr=kmp();
printf("%d\n",nr);
for(i=1;i<=minim(nr,1000);i++)
printf("%d ",pos[i]);
printf("\n");
return 0;
}