Cod sursa(job #876628)

Utilizator enedumitruene dumitru enedumitru Data 11 februarie 2013 22:56:14
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream> 
#define Nmax 2000002 
using namespace std;  
ifstream f("strmatch.in"); ofstream g("strmatch.out");
char a[Nmax], b[Nmax]; 
int pi[Nmax], poz[1002]; 
int main() 
{  f.getline(a,Nmax); f.getline(b,Nmax); 
   int nr=0; 
   int k=0,n=strlen(a),m=strlen(b);
   pi[0]=-1; 
   for(int j=1;j<n;++j)
   {  while(k && a[j]!=a[k]) k=pi[k-1]; 
      if(a[j]==a[k]) k++; 
      pi[j]=k; 
   } 
   k = 0; 
   for(int i=0;i<m;++i) 
   {  while(k && b[i]!=a[k]) k=pi[k-1]; 
      if(b[i]==a[k]) k++; 
      if(k==n) 
	  { if(nr<1000) poz[nr]=i-n+1; 
		nr++; k=pi[k-1]; 
      } 
   } 
   g<<nr<<'\n'; 
   for(int i=0;i<min(nr,1000);++i) g<<poz[i]<<" "; 
   return 0; 
}