Pagini recente » Cod sursa (job #2428772) | Cod sursa (job #2944909) | Cod sursa (job #1086818) | Cod sursa (job #2622590) | Cod sursa (job #1201946)
# 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 ] ++;
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 <= sol[ 0 ] ; i++ )
g << sol[ i ] << " ";
return 0;
}