Cod sursa(job #208087)

Utilizator nicolaetitus12Nicolae Titus nicolaetitus12 Data 14 septembrie 2008 07:08:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <cstring>
#include <cstdio>
#define N 2000003
char sir[N],sub[N];
long pi[N];
long poz[1000000],vf;
int main ()
{FILE *fin=fopen("strmatch.in","r");
 FILE *fout=fopen("strmatch.out","w");
 fgets(sub,N,fin);
 fgets(sir,N,fin);
 long i,j,l1=strlen(sir),l2=strlen(sub);
 l2--;
 for (i=l1;i>=1;i--)
 {sir[i]=sir[i-1];}
 for (i=l2;i>=1;i--)
 {sub[i]=sub[i-1];}
 *sir=' ';
 *sub=' ';
// for (i=1;i<=l1;i++) {pi[i]=1;}
 
 for (j=0,i=2;i<=l2;i++)
 {while(sub[j+1]!=sub[i]&&j>0)
  {j=pi[j];
  }
  if(sub[j+1]==sub[i])
  {j++;}
  pi[i]=j;
 }
 
 for (vf=0,j=0,i=1;i<=l1;i++)
 {while(sub[j+1]!=sir[i]&&j>0)
  {j=pi[j];
  }
  if(sub[j+1]==sir[i])
  {j++;
   if(j==l2)
   {poz[vf++]=i-l2;
    j=pi[j];
   }
  } 
 }
 
 fprintf(fout,"%ld\n",vf);
 for (i=0;i<vf;i++)
 {fprintf(fout,"%ld ",poz[i]);
 }
 fclose (fout);
 return 0;
}