Cod sursa(job #1518870)

Utilizator hristacheruxiRuxandra Hristache hristacheruxi Data 6 noiembrie 2015 15:35:08
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <cstdio>
#include <cstring>
#define B 123
#define MOD1 1000007
#define MOD2 1000021
#define N 2000000

char s1[N], s2[N];
int v[N];
int main()
{
    freopen("strmatch.in" , "r" , stdin);
    freopen("strmatch.out" , "w" , stdout);
    int n1,n2,i,x1=0,x2=0,y1=0,y2=0,put1=1,put2=1,cate;

    scanf("%s%s" , &s1, &s2);

    n1=strlen(s1);
    n2=strlen(s2);

    if(n1>n2)
        printf("0");
    else
    {

        for(i=0; i<n1; i++)
        {
            x1=((x1*B)+s1[i])%MOD1;
            x2=((x2*B)+s1[i])%MOD2;

            y1=((y1*B)+s2[i])%MOD1;
            y2=((y2*B)+s2[i])%MOD2;

            if(i>=1)
            {
                put1=(put1*B)%MOD1;
                put2=(put2*B)%MOD2;
            }
        }

        cate=0;
        if(x1==y1 && x2==y2)
            cate++;

        for(i=n1; i<=n2; i++)
        {
            y1=((((((y1-((s2[i-n1]*put1)%MOD1))+MOD1)%MOD1)*B)%MOD1)+s2[i])%MOD1;
            y2=((((((y2-((s2[i-n1]*put2)%MOD2))+MOD2)%MOD2)*B)%MOD2)+s2[i])%MOD2;

            if(x1==y1 && x2==y2)
            {
                cate++;
                if(cate<=1000)
                    v[cate]=i-n1+1;
            }
        }

        if(cate>1000)
            cate=1000;
        printf("%d\n" , cate);
        for(i=1; i<=cate; i++)
            printf("%d ", v[i]);
    }

    return 0;
}