Cod sursa(job #1514706)

Utilizator ASTELOTudor Enescu ASTELO Data 31 octombrie 2015 14:48:05
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include<cstdio>
#include<cstring>
#define n1 1000007
#define n2 1000021
char v[2000001],v2[2000001];
int sol[1001];
int main ()
{freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
int k1,k2,i,m1,m2,p1,p2,x1,x2,q=0;
scanf("%s%s",&v,&v2);
k1=strlen(v);
k2=strlen(v2);
x1=x2=1;
m1=0;
m2=0;
for(i=k1-1;i>=0;i--)
    {if(v[i]>='A'&&v[i]<='Z')
        {m1+=(v[i]-'A'+1)*x1;
        m2+=(v[i]-'A'+1)*x2;
        }
    else
        if(v[i]>='a'&&v[i]<='z')
            {m1+=(v[i]-'a'+1+26)*x1;
            m2+=(v[i]-'a'+1+26)*x2;
            }
        else
            {m1+=(v[i]-'0'+1+52)*x1;
            m2+=(v[i]-'0'+1+52)*x2;
            }
    m1=m1%n1;
    m2=m2%n2;
    x1=(x1*63)%n1;
    x2=(x2*63)%n2;
    }
x1=x2=1;
p1=0;
p2=0;
for(i=k1-1;i>=0;i--)
    {if(v2[i]>='A'&&v2[i]<='Z')
        {p1=(p1+(v2[i])*x1)%n1;
        p2=(p2+(v2[i])*x2)%n2;
        }
    else
        if(v2[i]>='a'&&v2[i]<='z')
            {p1=(p1+(v2[i])*x1)%n1;
            p2=(p2+(v2[i])*x2)%n2;
            }
        else
            {p1=(p1+(v2[i])*x1)%n1;
            p2=(p2+(v2[i])*x2)%n2;
            }
    p1=p1%n1;
    p2=p2%n2;
    x1=(x1*63)%n1;
    x2=(x2*63)%n2;
    }
x1=(x1/63)%n1;
x2=(x2/63)%n2;
if(m1==p1&&m2==p2)
    {q=1;
    sol[1]=0;
    }
for(i=1;i<k2-k1+1;i++)
    {if(v2[i-1]>='A'&&v2[i-1]<='Z')
        {p1=(p1-((v2[i-1])*x1)%n1+n1)%n1;
        p2=(p2-((v2[i-1])*x2)%n2+n2)%n2;
        }
    else
        if(v2[i-1]>='a'&&v2[i-1]<='z')
            {p1=(p1-((v2[i-1])*x1)%n1+n1)%n1;
            p2=(p2-((v2[i-1])*x2)%n2+n2)%n2;
            }
        else
            {p1=(p1-((v2[i-1])*x1)%n1+n1)%n1;
            p2=(p2-((v2[i-1])*x2)%n2+n2)%n2;
            }
    p1=(p1*63)%n1;
    p2=(p2*63)%n2;
    if(v2[i+k1-1]>='A'&&v2[i+k1-1]<='Z')
        {p1=(p1+(v2[i+k1-1]))%n1;
        p2=(p2+(v2[i+k1-1]))%n2;
        }
    else
        if(v2[i+k1-1]>='a'&&v2[i+k1-1]<='z')
            {p1=(p1+(v2[i+k1]))%n1;
            p2=(p2+(v2[i+k1]))%n2;
            }
        else
            {p1=(p1+(v2[i+k1-1]))%n1;
            p2=(p2+(v2[i+k1-1]))%n2;
            }
   // if(m1==p1&&m2==p2)
        {q++;
        if(q<=1000)
            sol[q]=p1;
        }

    }
printf("%d\n",q);
for(i=1;i<=q;i++)
    printf("%d ",sol[i]);
return 0;
}