Cod sursa(job #213227)

Utilizator katakunaCazacu Alexandru katakuna Data 8 octombrie 2008 22:04:09
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include<stdio.h>   
#include<algorithm>   
using namespace std;   
  
char a[2000111],b[2000111];   
int N,sol[2000111],n,m,i,q,pi[1024];   
  
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;   
}