Pagini recente » Cod sursa (job #2923333) | Cod sursa (job #2572678) | Cod sursa (job #2662870) | Cod sursa (job #1061365) | Cod sursa (job #216737)
Cod sursa(job #216737)
#include<string.h>
#include<stdio.h>
#define nmax 2000001
int main()
{
char a[nmax], b[nmax];
int t[nmax], p[1024],c=0, i,k,pos=2,cnd=0,la,lb;
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
fgets(a,nmax,stdin);
fgets(b,nmax,stdin);
la=strlen(a)-1;
lb=strlen(b)-1;
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( k<la && i+k<lb && a[k]==b[i+k] )
{
k++;
}
if(i+k==lb && k!=la) {i+=k; break; }
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;
}