Cod sursa(job #1206550)

Utilizator thesilverhand13FII Florea Toma Eduard thesilverhand13 Data 10 iulie 2014 15:00:05
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
 # include <fstream>
 # include <algorithm>
 # include <cstring>
 # include <vector>
 
 # define dim 2000005
 
 using namespace std;
 
 ifstream f("strmatch.in");
 ofstream g("strmatch.out");
 
 char a[ dim ], b[ dim ];
 int pre[ dim ], sol[ dim ];
 int lg , lg_b;
 
 void prefix()
 {
	 int i, q = 0;
	 pre[ 0 ] = 0;
	 
	 for ( i = 2 ; i <= lg ; i++ ){
		 while( q > 0 && a[ q + 1 ] != a[ i ] )
			 q = pre[ q ];
		 if ( a[ q + 1 ] == a[ i ] )
			 q++;
		 pre[ i ] = q;
	 }
 }
 
 void rezolva()
 {
	 int i, q = 0;
	 for ( i = 1 ; i <= lg_b ; i++ ){
		 while ( q > 0 && a[ q + 1 ] != b[ i ] )
			 q = pre[ q ];
		 if ( a[ q + 1 ] == b[ i ] )
			 q++;
		 if ( q == lg ){
			 sol[ 0 ] ++;
			 if ( sol[ 0 ] < 1000 )
				 sol[ sol[ 0 ] ] = i - lg;
			 q = pre[ q ];
		 }
	 }
 }
 
 void afiseaza()
 {
	 int i;
	 g << sol[ 0 ] << "\n";
	 for ( i = 1 ; i <= min( sol[ 0 ], 1000 ) ; i++ )
		 g << sol[ i ] << " ";
 }
 
 int main()
 {
	f >> ( a + 1 );
	f >> ( b + 1 );
	lg = strlen( a + 1 );
	lg_b = strlen( b + 1 );
	prefix();
	rezolva();
	afiseaza();
	return 0;
 }