Cod sursa(job #1687255)

Utilizator CodrutLemeniCodrut Lemeni CodrutLemeni Data 12 aprilie 2016 19:01:13
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define P 73
#define MOD1 100007
#define MOD2 100021
#define N 2000010
#define VERIF hs11==hs21 && hs12==hs22

using namespace std;

char sir1[N],sir2[N],v[N];

int main(){
    int p1,p2;
    int hs11,hs12,hs21,hs22;
    int nr=0;
    int len1,len2,i;

    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    scanf("%s %s",sir1,sir2);

    len1=strlen(sir1);
    len2=strlen(sir2);

    hs11=hs12=0;
    p1=p2=1;
    for(i=0;i<len1;i++){
        hs11=(hs11*P+sir1[i])%MOD1;
        hs12=(hs12*P+sir1[i])%MOD2;

        if(i==0){
            continue;
        }
        p1=p1 * P % MOD1;
        p2=p2 * P % MOD2;

    }

    hs21=hs22=0;
    for(i=0;i<len1;i++){
        hs21=( hs21 * P + sir2[i] )%MOD1;
        hs22= (hs22 * P + sir2[i] )%MOD2;
    }
    if(VERIF){
        v[nr++]=0;
    }

    for(i=len1;i<len2;i++){
        hs21 = ((hs21 - (sir2[i - len1] * p1) % MOD1 + MOD1) * P + sir2[i]) % MOD1;
        hs22 = ( (hs22 - (sir2[i - len1] * p2) % MOD2 + MOD2) * P + sir2[i]) % MOD2;

        if(VERIF){
            v[nr++]=i-len1+1;
        }
    }

    printf("%d\n",nr);

    for(i=0;i<nr;i++){
        printf("%d ",v[i]);
    }

    return 0;
}