Pagini recente » Rating Sorin Olimpicu (sorin_olimpicu23) | Cod sursa (job #1730846) | Cod sursa (job #3282085) | Cod sursa (job #1549044) | Cod sursa (job #1206554)
# 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;
}