Pagini recente » Cod sursa (job #1621536) | Cod sursa (job #531321) | Cod sursa (job #1940016) | Cod sursa (job #2601875) | Cod sursa (job #1915248)
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define NMAX 2000002
#define MOD1 100007
#define MOD2 100021
#define BAZA 101
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 valk1, valk2;
int hash1, hash2;
hash1 = hash2 = 0;
valk1 = valk2 = 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 ) {
valk1 = ( valk1 * BAZA + A[ i ] ) % MOD1;
valk2 = ( valk2 * BAZA + A[ i ] ) % MOD2;
if ( i != 0 ) {
p1 = ( p1 * BAZA ) % MOD1;
p2 = ( p2 * BAZA ) % MOD2;
}
}
for ( i = 0; i < n; ++i ) {
hash1 = ( hash1 * BAZA + B[ i ] ) % MOD1;
hash2 = ( hash2 * BAZA + B[ i ] ) % MOD2;
}
if ( hash1 == valk1 && hash2 == valk2 ) Q.push( 0 );
for ( i = n; i < m; ++i ) {
hash1 = ( ( hash1 - ( B[ i - n ] * p1 ) % MOD1 + MOD1 ) * BAZA + B[ i ] ) % MOD1;
hash2 = ( ( hash2 - ( B[ i - n ] * p2 ) % MOD2 + MOD2 ) * BAZA + B[ i ] ) % MOD2;
if ( hash1 == valk1 && hash2 == valk2 )
Q.push( i - n + 1 );
}
printf( "%d\n",Q.size() );
m = 0;
while ( !Q.empty() && m < 1000 ) {
printf( "%d ",Q.front() );
Q.pop();
m++;
}
return 0;
}