Cod sursa(job #454738)

Utilizator emanuela.hallerHaller Emanuela emanuela.haller Data 12 mai 2010 13:15:16
Problema Potrivirea sirurilor Scor 36
Compilator c Status done
Runda Arhiva educationala Marime 0.85 kb
#include<stdio.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()
   {
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    
    gets(a);
    gets(b);
    m=strlen(a);
    n=strlen(b);
    
   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) 
         {
          ls++;
          s[ls]=i-m;
          q=v[q];
         }
      }
      printf("%i\n",ls);
    for (i=1;i<=ls;i++)
       printf("%i ",s[i]);    
    return 0;
   }