Cod sursa(job #1741394)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 13 august 2016 20:02:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <cstdio>
#define MAXN 2000000
#define MAXP 1000
char A[MAXN+2],B[MAXN+2];
int pi[MAXN+1];
int rez[MAXP];
int con;
inline void Calc_Prefix(char *A,int n){
    int i,k;
    pi[1]=0;
    k=0;
    for(i=2;i<=n;i++){
        while(k>0&&A[k+1]!=A[i])
          k=pi[k];
        if(A[k+1]==A[i])
          k++;
        pi[i]=k;
    }
}
inline void Potrivire(char *A,char *B,int n,int m){
    int i,k;
    k=0;
    for(i=1;i<=m;i++){
        while(k>0&&A[k+1]!=B[i])
          k=pi[k];
        if(A[k+1]==B[i])
          k++;
        if(k==n){
           con++;
           if(con<=MAXP)
             rez[con]=i-n;
        }
    }
}
int main(){
   FILE*fi,*fout;
   int n,i,m;
   char a;
   fi=fopen("strmatch.in" ,"r");
   fout=fopen("strmatch.out" ,"w");
   a=fgetc(fi);
   n=0;
   while(a!='\n'){
      A[++n]=a;
      a=fgetc(fi);
   }
   A[n+1]=-1;
   a=fgetc(fi);
   m=0;
   while(a!='\n'){
      B[++m]=a;
      a=fgetc(fi);
   }
   Calc_Prefix(A,n);
   Potrivire(A,B,n,m);
   fprintf(fout,"%d\n" ,con);
   for(i=1;i<=con&&i<=MAXP;i++)
     fprintf(fout,"%d " ,rez[i]);
   fclose(fi);
   fclose(fout);
   return 0;
}