Cod sursa(job #1516290)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 2 noiembrie 2015 22:15:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <cstdio>
#define MAXN 2000000
char v[2*MAXN+1];
int z[2*MAXN+1];
int main(){
    FILE*fi,*fout;
    int n,con,j,i,l,r,nr;
    fi=fopen("strmatch.in" ,"r");
    fout=fopen("strmatch.out" ,"w");
    n=0;
    while(v[n]!='\n')
        v[++n]=fgetc(fi);
    n--;
    nr=n;
    while(v[n]!='\n')
        v[++n]=fgetc(fi);
    l=r=0;
    z[1]=n;
    for(i=2;i<=n-nr;i++)
        if(r<i){
            j=i;
            while(j<n&&v[j]==v[j-i+1])
                j++;
            if(r<j-1&&j-1>=i){
               l=i;
               r=j-1;
            }
            z[i]=j-i;
        }
        else
            if(z[i-l+1]<r-i+1)
                 z[i]=z[i-l+1];
            else{
                j=r+1;
                while(j<n&&v[j]==v[j-i+1])
                   j++;
                r=j-1;
                l=i;
                z[i]=j-i;
            }
    con=0;
    for(i=nr+1;i<n;i++)
        if(z[i]>=nr)
             con++;
    fprintf(fout,"%d\n" ,con);
    if(con>1000)
        con=1000;
    i=nr+1;
    while(con){
        if(z[i]>=nr){
            fprintf(fout,"%d " ,i-nr-1);
            con--;
        }
        i++;
    }
    fclose(fi);
    fclose(fout);
    return 0;
}