Cod sursa(job #454756)

Utilizator emanuela.hallerHaller Emanuela emanuela.haller Data 12 mai 2010 13:32:39
Problema Potrivirea sirurilor Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 0.93 kb
#include<stdio.h>
#include<string.h>
#define MAX 2000005
char a[MAX], b[MAX];
long v[MAX],n,m;

void prefix(void)
   {
    int k,q;
    v[0]=0;
    k=0;
    for(q=2;q<=m;q++)
       {
        while (k>0 && a[k]!=a[q-1]) k=v[k];
        if (a[k]==a[q-1]) 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;
    
   prefix();    
   
    
   long q,i;
   long ls=0,s[MAX];
   
   q=0;
   for (i=1;i<=n;i++)  
      {
       while (q>0 && a[q]!=b[i-1]) q=v[q];
       if (a[q]==b[i-1]) q++;
       if (q==m) 
         {
          if (ls<1000)
            {ls++;
          s[ls]=i-m;}
          q=v[q];
         }
      }
      fprintf(g,"%li\n",ls);
    for (i=1;i<=ls;i++)
       fprintf(g,"%li ",s[i]);    
    return 0;
   }