Cod sursa(job #1515699)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 2 noiembrie 2015 08:30:33
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 2.36 kb
#include <stdio.h>
#define BAZA 63
#define MOD1 100007
#define MOD2 100021
#define lg 2000000
char a[lg],b[lg];
int v[1000];
int CONV(char ch){
    if(ch>='0'&&ch<='9')
        return ch-'0'+1;
    if(ch>='A'&&ch<='Z')
        return ch-'A'+11;
    if(ch>='a'&&ch<='z')
        return ch-'a'+37;
}
int verific(int m,int n){
    int i,j,pp=0;
    for(i=0,j=m-n;i<=n;i++,j++)
        if(a[i]!=b[j])
            pp=1;
    if(pp==0)
        return m-n;
    else
        return 0;
}
int main(){
    FILE *fin,*fout;
    fin=fopen("strmatch.in","r");
    fout=fopen("strmatch.out","w");
    int n,m,i,nra1,nra2,nrb1,nrb2,cate,poz;
    int PUT1=1,PUT2=1;
    char ch;
    n=0;
    nra1=0;
    nra2=0;
    ch=fgetc(fin);
    while(ch!='\n'){
        a[n]=ch;
        n++;
        nra1=((long long)nra1*BAZA+CONV(ch))%MOD1;
        nra2=((long long)nra2*BAZA+CONV(ch))%MOD2;
        ch=fgetc(fin);
    }
    n--;
    m=0;
    nrb1=0;
    nrb2=0;
    ch=fgetc(fin);
    while(m<=n&&ch!='\n'&&ch!=EOF){
        b[m]=ch;
        nrb1=((long long)nrb1*BAZA+CONV(ch))%MOD1;
        nrb2=((long long)nrb2*BAZA+CONV(ch))%MOD2;
        if(m<n){
            PUT1=(PUT1*BAZA)%MOD1;
            PUT2=(PUT2*BAZA)%MOD2;
        }
        m++;
        ch=fgetc(fin);
    }
    m--;
    cate=-1;
    if(nra1==nrb1&&nra2==nrb2){
        //poz=verific(m,n);
        //if(poz>=0){
            poz=m-n;
            cate++;
            if(cate<1000)
                v[cate]=poz;
        //}
    }
    if(m==n&&ch!='\n'&&ch!=EOF){
        while(ch!='\n'){
            m++;
            b[m]=ch;
            nrb1=(nrb1-(long long)(CONV(b[m-n-1])*PUT1)%MOD1+MOD1)%MOD1;
            nrb1=((long long)nrb1*BAZA+CONV(b[m]))%MOD1;
            nrb2=(nrb2-(long long)(CONV(b[m-n-1])*PUT2)%MOD2+MOD2)%MOD2;
            nrb2=((long long)nrb2*BAZA+CONV(b[m]))%MOD2;
            if(nra1==nrb1&&nra2==nrb2){
                //poz=verific(m,n);
                //if(poz>=0){
                    poz=m-n;
                    cate++;
                    if(cate<1000)
                        v[cate]=poz;
                //}
            }
            ch=fgetc(fin);
        }
    }
    fprintf(fout,"%d\n",cate+1);
    if(cate>999)
        cate=999;
    for(i=0;i<=cate;i++)
        fprintf(fout,"%d ",v[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}