Cod sursa(job #1518842)

Utilizator Alex.PAlexandru Pacurar Alex.P Data 6 noiembrie 2015 15:16:19
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 1.56 kb
#include <stdio.h>
#include <stdlib.h>

int p[2000000];
int s[2000000];
int v[2000000];

int main()
{
    int l1,l2,mr1,mr2,nr1,nr2,n1,n2,p1,p2,b,i,j,gasit=0;
    char c;
    FILE *fin, *fout;
    fin=fopen("strmatch.in","r");
    fout=fopen("strmatch.out","w");
    c=fgetc(fin);
    while(c==' ' || c=='/n'){
        c=fgetc(fin);
    }
    i=0;
    while(c!=' ' && c!='/n'){
        p[i];
        i++;
        c=fgetc(fin);
    }
    l2=i;
    while(c==' ' || c=='/n'){
        c=fgetc(fin);
    }
    i=0;
    while(c!=' ' && c!='/n' && c!=EOF){
        s[i];
        i++;
        c=fgetc(fin);
    }
    l1=i;
    n1=100007;
    n2=100021;
    nr1=nr2=0;
    p1=p2=1;
    b=123;
    for(i=0;i<l2;i++){
        nr1=(nr1*b+p[i])%n1;
        nr2=(nr2*b+p[i])%n2;
        if(i>=1){
            p1=(p1*b)%n1;
            p2=(p2*b)%n2;
        }
    }
    mr1=mr2=0;
    for(i=0;i<l2;i++){
        mr1=(nr1*b+s[i])%n1;
        mr2=(nr2*b+s[i])%n2;
    }
    if(l1<l2)
        fprintf(fout,"0");
    else{
        if(nr1==mr1 && nr2==mr2){
            v[gasit]=0;
            gasit++;
        }
        for(i=0,j=l2;j<l1;i++,j++){
            mr1=(((mr1-s[i]*p1%n1)+n1)%n1*b+s[j])%n1;
            mr2=(((mr2-s[i]*p2%n2)+n2)%n2*b+s[j])%n2;
        }
        if(nr1==mr1 && nr2==mr2){
            if(gasit<1000)
                v[gasit]=i+1;
            gasit++;
        }
    }
    fprintf(fout,"%d/n",gasit);
    for(i=0;i<gasit;i++){
        fprintf(fout,"%d ",v[i]);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}