Cod sursa(job #1528503)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 19 noiembrie 2015 19:32:19
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <cstdio>
#define MAXN 2000000
FILE*fi,*fout;
char v1[MAXN+1],v2[MAXN+1],poz[1000],a;
int pi[MAXN+1];
inline int cit(char *v){
    int n=0;
    a=fgetc(fi);
    while(a!='\n'){
        v[++n]=a;
        a=fgetc(fi);
    }
    return n;
}
inline void cauta(char *v,int n){
    int i,j;
    pi[1]=0;
    for(i=2;i<=n;i++){
        if(v[i]==v[pi[i-1]+1])
            pi[i]=pi[i-1]+1;
        else{
            j=i-1;
            while(j>1&&v[pi[j]+1]!=v[i])
                j=pi[j];
            pi[i]=pi[j];
            if(v[i]==v[1]&&pi[i]==0)
                pi[i]=1;
        }
    }
}
int main(){
    int n,m,i,kmp,con;
    fi=fopen("strmatch.in" ,"r");
    fout=fopen("strmatch.out" ,"w");
    n=cit(v1);
    m=cit(v2);
    cauta(v1,n);
    kmp=con=0;
    for(i=1;i<m;i++){
        while(v2[i]!=v1[kmp+1]&&kmp!=0)
            kmp=pi[kmp];
        if(v2[i]==v1[kmp+1])
            kmp++;
        if(kmp==n)
            if(con<1000)
                poz[con++]=i-kmp;
    }
    fprintf(fout,"%d\n" ,con);
    for(i=0;i<con;i++)
        fprintf(fout,"%d " ,poz[i]);
    fclose(fi);
    fclose(fout);
    return 0;
}