Pagini recente » Cod sursa (job #397119) | Cod sursa (job #1773474) | Cod sursa (job #2242828) | Cod sursa (job #2301978) | Cod sursa (job #1915176)
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define NMAX 2000002
#define MOD1 100007
#define MOD2 100021
#define BAZA 73
char A[ NMAX ];
char B[ NMAX ];
queue < int > Q;
int main () {
freopen( "strmatch.in", "r", stdin );
freopen( "strmatch.out", "w", stdout );
int n, m, i, j, x, y, p1, p2;
int cod_sablon1, cod_sablon2;
int cod_cautare1, cod_cautare2;
cod_cautare1 = cod_cautare2 = 0;
cod_sablon1 = cod_sablon2 = 0;
p1 = p2 = 1;
scanf( "%s%s",&A,&B );
n = strlen( A );
m = strlen( B );
if ( n > m ) {
printf( "0\n" );
return 0;
}
for ( i = 0; i < n; ++i ) {
cod_sablon1 = ( cod_sablon1 * BAZA + A[ i ] ) % MOD1;
cod_sablon2 = ( cod_sablon2 * BAZA + A[ i ] ) % MOD2;
if ( i > 0 ) {
p1 = ( p1 * BAZA ) % MOD1;
p2 = ( p2 * BAZA ) % MOD2;
}
}
for ( i = 0; i < n; ++i ) {
cod_cautare1 = ( cod_cautare1 * BAZA + B[ i ] ) % MOD1;
cod_cautare2 = ( cod_cautare2 * BAZA + B[ i ] ) % MOD2;
}
if ( cod_cautare1 == cod_sablon1 && cod_cautare2 == cod_sablon2 ) Q.push( 0 );
for ( i = n; i <= m; ++i ) {
cod_cautare1 = ( ( cod_cautare1 - B[ i - n ] * p1 % MOD1 + MOD1 ) * BAZA + B[ i ] ) % MOD1;
cod_cautare2 = ( ( cod_cautare2 - B[ i - n ] * p2 % MOD2 + MOD2 ) * BAZA + B[ i ] ) % MOD2;
if ( cod_cautare1 == cod_sablon1 && cod_cautare2 == cod_sablon2 ) Q.push( i - n + 1 );
}
printf( "%d\n",Q.size() );
while ( !Q.empty() ) {
printf( "%d ",Q.front() );
Q.pop();
}
return 0;
}