Cod sursa(job #1982171)

Utilizator ioana.jianuIoana Jianu ioana.jianu Data 17 mai 2017 19:59:50
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int s1,s2,n,m,i,k,p62;
int v[2000001],a[2000001],b[2000001];
char sir1[2000001],sir2[2000001];

int functie(int MOD,int s){
    int x;

    x=b[i-n]*p62;
    x=(s+MOD-x)%MOD;
    x=(x*62+b[i])%MOD;
    return x;
}




int main(){

    FILE *fin,*fout;
    fin=fopen("strmatch.in","r");
    fout=fopen("strmatch.out","w");

    int MOD,ref1,ref2,p,l;

    fscanf(fin,"%s%s",sir1,sir2);

    n=strlen(sir1);
    for(i=0;i<n;i++){
        if(sir1[i]>='a'&&sir1[i]<='z')
            a[i+1]=sir1[i]-'a'+26;
        if(sir1[i]>='A'&&sir1[i]<='Z')
            a[i+1]=sir1[i]-'A';
        if(sir1[i]>='0'&&sir1[i]<='9')
            a[i+1]=sir1[i]-'0'+52;
    }

    m=strlen(sir2);
    for(i=0;i<m;i++){
        if(sir2[i]>='a'&&sir2[i]<='z')
            b[i+1]=sir2[i]-'a'+26;
        if(sir2[i]>='A'&&sir2[i]<='Z')
            b[i+1]=sir2[i]-'A';
        if(sir2[i]>='0'&&sir2[i]<='9')
            b[i+1]=sir2[i]-'0'+52;
    }

    MOD=666013;
    ref1=0;
    p=1;
    for(i=n;i>=1;i--){
        ref1=(ref1+p*a[i])%MOD;
        p*=62;
    }

    MOD=1000003;
    ref2=0;
    p=1;
    for(i=n;i>=1;i--){
        ref2=(ref2+p*a[i])%MOD;
        p*=62;
    }

    MOD=666013;
    s1=0;
    p=1;
    for(i=n;i>=1;i--){
        s1=(s1+p*b[i])%MOD;
        p*=62;
    }
    MOD=1000003;
    s2=0;
    p=1;
    for(i=n;i>=1;i--){
        s2=(s2+p*b[i])%MOD;
        p*=62;
    }
    k=0;
    if(s1==ref1&&s2==ref2){
        k++;
        v[k]=1;
    }

    p62=1;
    for(l=1;l<n;l++)
        p62=p62*62%MOD;

    for(i=n+1;i<=m;i++){
        s1=functie(666013,s1);
        s2=functie(1000003,s2);
        if(s1==ref1&&s2==ref2){
            k++;
            v[k]=i-n;
        }
    }

    fprintf(fout,"%d\n",k);
    for(i=1;i<=k;i++)
        fprintf(fout,"%d ",v[i]);

    fclose(fin);
    fclose(fout);

    return 0;
}