Cod sursa(job #1513850)

Utilizator NastureNasture Anca Nasture Data 30 octombrie 2015 08:40:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <stdio.h>
#include <string.h>
#define N1 100007
#define N2 100021
char s1[2000001], s2[2000001];
int Ns1, Ns2;
int nrs1, nrs2, p1, p2;
char v[2000001];
int main(){
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s%s",&s1,&s2);
    Ns1=strlen(s1);
    Ns2=strlen(s2);
    p1=p2=1;
    nrs1=nrs2=0;
    for (int i=0;i<Ns1;i++){
        nrs1=(nrs1*73+s1[i])% N1;
        nrs2=(nrs2*73+s1[i])% N2;
        if (i!=0)
            p1=(p1*73)% N1,
            p2=(p2*73)%N2;
    }
    if (Ns1>Ns2){
        printf("0\n");
    }
    else{
        int nr1=0,nr2=0;
        for (int i=0;i<Ns1;i++){
            nr1=(nr1*73+s2[i])%N1;
            nr2=(nr2*73+s2[i])%N2;
        }
        int k=0;
        if (nr1==nrs1&&nr2==nrs2){
            v[0]=1;
            k++;
        }
        for (int i=Ns1;i<Ns2;i++){
            nr1=((nr1-(s2[i-Ns1]*p1)%N1+N1)*73+s2[i])%N1;
            nr2=((nr2-(s2[i-Ns1]*p2)%N2+N2)*73+s2[i])%N2;
            if (nr1==nrs1&&nr2==nrs2){
                v[i-Ns1+1]=1;
                k++;
            }
        }
        printf("%d\n",k);
        k = 0;
        for (int i=0;i<Ns2&&k<1000;i++)
            if(v[i]==1){
                k++;
                printf("%d ",i);
            }
        printf("\n");
    }
    return 0;
}