Cod sursa(job #1518654)

Utilizator hristacheruxiRuxandra Hristache hristacheruxi Data 6 noiembrie 2015 06:51:55
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 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);

    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++;
        v[cate]=0;
    }

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

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

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

    return 0;
}