Cod sursa(job #213214)

Utilizator katakunaCazacu Alexandru katakuna Data 8 octombrie 2008 21:53:35
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

char a[2000111],b[2000111];
int N,sol[1024],n,m,i,q,pi[2000111];

int min(int a,int b){
 if(a<b)
 return a;

return b;
}

int main(){

FILE *f=fopen("strmatch.in","r");
FILE *g=fopen("strmatch.out","w");
fscanf(f,"%s",a+1);
fscanf(f,"%s",b+1);

q=pi[1]=0;
a[0]=b[0]=' ';
n=strlen(a);
m=strlen(b);
n--;
m--;

   for(i=2;i<=n;i++){

     while(q && a[q+1]!=a[i])
     q=pi[q];

     if(a[q+1] == a[i] )
     q++;

     pi[i]=q;

   }

q=0;


   for(i=1;i<=m;i++){

      while(q && a[q+1] != b[i])
      q=pi[q];

      if(a[q+1] == b[i])
      q++;

      if(q==n){
      q=pi[q];
      N++;
      sol[N]=i-n;
      }

   }

   fprintf(g,"%d\n",N);

   for(i=1;i<=min(N,1000);i++)
   fprintf(g,"%d ",sol[i]);

fclose(f);
fclose(g);

return 0;
}