Cod sursa(job #454934)

Utilizator emanuela.hallerHaller Emanuela emanuela.haller Data 12 mai 2010 20:37:20
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 1.07 kb
#include<stdio.h>
#include<string.h>

#define MAX 2000005
char a[MAX], b[MAX];
long v[MAX],n,m;

void prefix()
   {
    int k,q;
    v[1]=0;
    k=0;
    for(q=2;q<=m;q++)
       {
        while (k>0 && a[k+1]!=a[q]) k=v[k];
        if (a[k+1]==a[q]) k++;
        v[q]=k;
       }
   }
   

int main()
   {
   FILE *f=fopen("strmatch.in","rt");
   FILE *g=fopen("strmatch.out","wt");
   
    fgets(a,MAX,f);
    fgets(b,MAX,f);
    m=strlen(a)-1;
    n=strlen(b)-1;
    long i;
    for(i=m;i>=1;i--) a[i]=a[i-1];
    for(i=n;i>=1;i--) b[i]=b[i-1]; 
    a[0]=' ';
    b[0]=' ';
    
    prefix();    

    long q;
    long ls=0,s[MAX];
   
    q=0;
    for (i=1;i<=n;i++)  
      {
       while (q>0 && a[q+1]!=b[i]) q=v[q];
       if (a[q+1]==b[i]) q++;
       if (q==m) 
         {ls++;
          if (ls<=1000)
            {
          s[ls]=i-m;}
          q=v[q];
         }
      }
    
    fprintf(g,"%li\n",ls);
    for (i=1;i<=ls;i++)
       fprintf(g,"%li ",s[i]);    
     
     fclose(f);
     fclose(g);
     return 0;
   }