Cod sursa(job #1201948)

Utilizator legionarulCorneliu Zelea Codreanu legionarul Data 26 iunie 2014 15:04:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
 # include <fstream>
 # include <cstring>
 # include <algorithm>
 
 # define dim1 2000005
 # define dim2 1005
 
 using namespace std;
 
 ifstream f("strmatch.in");
 ofstream g("strmatch.out");
 
 char a[ dim1 ], b[ dim1 ];
 int p[ dim1 ], sol[ dim1 ];
 int lga, lgb;
 
 void calculeaza()
 {
	 int i, q = 0;
	 for ( i = 1 ; i <= lgb ; i++ )
	 {
		 while ( q > 0 && a[ q + 1 ] != b[ i ] )
			 q = p[ q ];
		 if ( a[ q + 1 ] == b[ i ] )
			 q++;
		 if ( q == lga )
		 {
			 sol[ 0 ] ++;
			 if ( sol[ 0 ] <= 1000 )
				 sol[ sol[ 0 ] ] = i - lga;
			 q = p[ q ];
		 }
	 }
 }
 
 void prefix()
 {
	 int i, q = 0;
	 p[ 1 ] = 0 ; // pentru ca prima litera, nu poate avea prefix
	 for ( i = 2 ; i <= lga ; i++ ) // comparam primele 1..q litere cu i...n litere
	 {
		 while ( q > 0 && a[ q + 1 ] != a[ i ] ) /// in caz de nepotrivire, ne intoarcem
			 q = p[ q ];
		 if ( a[ q + 1 ] == a[ i ] ) // in caz de potrivire, crestem prefixul( care e si sufix ) si continuam
			 q++;
		 p[ i ] = q;
	 }
	 //g << " ";
	 //for ( i = 1 ; i <= lga ; i++ )
		// g << p[ i ];
 }
 
 void citire()
 {
	 int i;
	
	 f.getline( a ,sizeof( a ) );
	 f.getline( b ,sizeof( b ) );
	 
	 lga = strlen( a );
	 lgb = strlen( b );
	 
	 for ( i = lga ; i >= 1 ; i-- )
		 a[ i ] = a[ i - 1 ];
	 a[ 0 ] = ' ' ;
	 for ( i = lgb ; i >= 1 ; i-- )
		 b[ i ] = b[ i - 1 ];
	 b[ 0 ] = ' ' ;
	 
	// g << a << "\n";
	 //g << b;
 }
 
 int main()
 {
	 int i;
	 citire();
	 prefix();
	 calculeaza();
	 g << sol[ 0 ] << "\n";
	 for ( i = 1 ; i <= min( sol[ 0 ], 1000 ) ; i++ )
		 g << sol[ i ] << " ";
	 return 0;
 }