Cod sursa(job #1518151)

Utilizator ipus1Stefan Enescu ipus1 Data 5 noiembrie 2015 17:23:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include<cstdio>
#include<cstring>
#define N1 100007
#define N2 100021
char s[2000001],p[2000001];
int v[1001];
int main(){
    int nr1,nr2,nnr1,nnr2, i,k1,k2,x1=1,x2=1,k;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s%s",&p,&s);
    nr1=nr2=0;
    k1=strlen(p);
    k2=strlen(s);
    for(i=0;i<k1;i++){
        nr1=(nr1*123+p[i])%N1;
        nr2=(nr2*123+p[i])%N2;
        if(i>=1){
            x1=(x1*123)%N1;
            x2=(x2*123)%N2;
        }
    }
    if(k1>k2){
        printf("0");
        return 0;
    }
    nnr1=nnr2=0;
    for(i=0;i<k1;i++){
        nnr1=(nnr1*123+s[i])%N1;
        nnr2=(nnr2*123+s[i])%N2;
    }
    k=0;
    if(nr1==nnr1&&nr2==nnr2){
        k++;
        v[k]=0;
    }
    for(i=k1;i<k2;i++){
        nnr1=(((nnr1-(s[i-k1]*x1)%N1+N1)%N1)*123+s[i])%N1;
        nnr2=(((nnr2-(s[i-k1]*x2)%N2+N2)%N2)*123+s[i])%N2;
        if(nr1==nnr1&&nr2==nnr2){
            k++;
            if(k<=1000)
                v[k]=i-k1+1;
        }
    }
    printf("%d\n",k);
    for(i=1;i<=k&&i<=1000;i++)
        printf("%d ",v[i]);
    return 0;
}