Cod sursa(job #1517599)

Utilizator lauratalaatlaura talaat lauratalaat Data 4 noiembrie 2015 16:57:09
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include<stdio.h>
#include<cstring>
#define n1 100007
#define n2 100021
#define b 123
char p[2000001],s[2000001];
int v[2000001];
int main(){
    int i,n,k,x,nr,B,nr1,nr2,p1,p2,k1,k2,nnr1,nnr2,j;
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s%s",&p,&s);
    k1=strlen(p);
    k2=strlen(s);
    nr1=nr2=0;
    p1=1;
    p2=1;
    for(i=0;i<k1;i++){
        nr1=((nr1*b)%n1+p[i])%n1;
        nr2=((nr2*b)%n2+p[i])%n2;
        if(i!=0){
            p1=(p1*b)%n1;
            p2=(p2*b)%n2;
        }
    }
    nnr1=nnr2=0;

    for(i=0;i<k1;i++){
        nnr1=((nnr1*b)%n1+s[i])%n1;
        nnr2=((nnr2*b)%n2+s[i])%n2;

    }
    k=0;
    if(nr1==nnr1&&nr2==nnr2){
        k++;
        v[k]=0;
    }
    for(i=0,j=k1;j<k2;i++,j++){
        nnr1=((((nnr1-(s[i]*p1))*b)%n1+n1)%n1+s[j])%n1;
        nnr2=((((nnr2-(s[i]*p2))*b)%n2+n2)%n2+s[j])%n2;
        if(nr1==nnr1&&nr2==nnr2){
            k++;
            v[k]=i+1;
            if(k>=1001)
                j=k2;
        }
    }
    printf("%d\n",k);
    for(i=1;i<=k&&i<=1000;i++)
        printf("%d ",v[i]);
    return 0;
}