Cod sursa(job #1514712)

Utilizator ipus1Stefan Enescu ipus1 Data 31 octombrie 2015 14:59:19
Problema Potrivirea sirurilor Scor 6
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include<cstdio>
#include<cstring>
char v[2000001],v2[2000001];
int p[2000001],s[2000001],sol[1001];
int main ()
{freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
int k1,k2,i,x,k,q;
scanf("%s%s",&v,&v2);
k1=strlen(v);
k2=strlen(v2);
for(i=k1;i>=0;i--)
    v[i+1]=v[i];
for(i=k2;i>=0;i--)
    v2[i+1]=v2[i];
v[0]=v2[0]=0;
for(i=2;i<=k1;i++)
    {if(v[i]==v[p[i-1]+1])
        p[i]=p[i-1]+1;
    else
        {p[i]=p[i-1];
        while(v[i]!=v[p[i]+1]&&p[i]!=0)
            p[i]=p[p[i]];
        if(p[i]>0||v[i]==v[1])
            p[i]++;
        }
    }
q=0;
for(i=1;i<=k2;i++)
    {if(v2[i]==v[s[i-1]+1]&&s[i-1]!=k1)
        s[i]=s[i-1]+1;
    else
        {s[i]=s[i-1];
        if(s[i-1]==k1)
            s[i]--;
        while(v2[i]!=v[s[i]+1]&&s[i]!=0)
            s[i]=s[s[i]];
        if(s[i]>0||v2[i]==v[1])
            s[i]++;
        }
    if(s[i]==k1)
        {q++;
        if(q<=1000)
            sol[q]=i-k1;
        }
    }
printf("%d\n",q);
if(q>1000)
    q=1000;
for(i=1;i<=q;i++)
    printf("%d ",sol[i]);
return 0;
}