Pagini recente » Cod sursa (job #382450) | Cod sursa (job #2000393) | Cod sursa (job #801895) | Cod sursa (job #1239159) | Cod sursa (job #216731)
Cod sursa(job #216731)
#include<string.h>
#include<stdio.h>
#define nmax 2000001
int main()
{
char a[nmax], b[nmax];
int t[nmax], p[1001],c=0, i,k,pos=2,cnd=0,la,lb;
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
gets(a);
gets(b);
la=strlen(a);
lb=strlen(b);
t[0]=-1;
t[1]=0;
while(pos<la)
{
if(a[pos-1]==a[cnd])
{
t[pos]=cnd+1;
cnd++;
pos++;
}
else if(cnd>0)
cnd=t[cnd];
else
{
t[pos]=0;
pos++;
}
}
// for(i=0;i<la;i++)
// printf("%d ", t[i]);
i=0;
k=0;
while(i<lb)
{
while(a[k]!=b[i] && i<lb) i++;
while(a[k]==b[i+k] && k<la && i+k<lb)
{
k++;
}
if(k==la)
{
p[c++]=i;
if(c==1000) {break;}
i+=k-t[k-1]-1;
k=t[k-1];
}
else
{
i+=k-t[k];
k=t[k];
}
}
printf("%d\n", c);
for(i=0;i<c;i++)
printf("%d ", p[i]);
printf("\n");
return 0;
}