Cod sursa(job #1515693)

Utilizator AnaRaduAna-Maria Radu AnaRadu Data 2 noiembrie 2015 08:22:48
Problema Potrivirea sirurilor Scor 80
Compilator c Status done
Runda Arhiva educationala Marime 1.9 kb
#include <stdio.h>
#define BAZA 63
#define MOD 100007
#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,nra,nrb,cate,poz;
    int PUT=1;
    char ch;
    n=0;
    nra=0;
    ch=fgetc(fin);
    while(ch!='\n'){
        a[n]=ch;
        n++;
        nra=((long long)nra*BAZA+CONV(ch))%MOD;
        ch=fgetc(fin);
    }
    n--;
    m=0;
    nrb=0;
    ch=fgetc(fin);
    while(m<=n&&ch!='\n'&&ch!=EOF){
        b[m]=ch;
        nrb=((long long)nrb*BAZA+CONV(ch))%MOD;
        if(m<n)
            PUT=(PUT*BAZA)%MOD;
        m++;
        ch=fgetc(fin);
    }
    m--;
    cate=-1;
    if(nra==nrb){
        poz=verific(m,n);
        if(poz>=0){
            cate++;
            if(cate<1000)
                v[cate]=poz;
        }
    }
    if(m==n&&ch!='\n'&&ch!=EOF){
        while(ch!='\n'){
            m++;
            b[m]=ch;
            nrb=(nrb-(long long)(CONV(b[m-n-1])*PUT)%MOD+MOD)%MOD;
            nrb=((long long)nrb*BAZA+CONV(b[m]))%MOD;
            if(nra==nrb){
                poz=verific(m,n);
                if(poz>0){
                    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;
}