Pagini recente » Cod sursa (job #276927) | Cod sursa (job #2666732) | Cod sursa (job #1144794) | Cod sursa (job #18444) | Cod sursa (job #629460)
Cod sursa(job #629460)
#include <cstdio>
#include <iostream>
#include <cstring>
#define MaxN 2000005
#define MaxS 1002
using namespace std;
const int P = 73, MOD1 = 100007, MOD2 = 666013;
char A[ MaxN ], B[ MaxN ];
int NA, NB, hashA1, hashA2, hashB1, hashB2, i, P1 = 1, P2 = 1, poz[ MaxS ], nrSol;
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin >> A >> B;
NA = strlen( A ); NB = strlen( B );
if( NA > NB )
{
printf("0\n");
return 0;
}
for( i = 0; i < NA ; ++i )
{
hashA1 = ( hashA1 * P + A[ i ] ) % MOD1 ;
hashA2 = ( hashA2 * P + A[ i ] ) % MOD2 ;
if( i > 0 )
{
P1 = ( P1 * P ) % MOD1;
P2 = ( P2 * P ) % MOD2;
}
}
for( i = 0; i < NA ; ++i )
{
hashB1 = ( hashB1 * P + B[ i ] ) % MOD1;
hashB2 = ( hashB2 * P + B [ i ] ) % MOD2;
}
if( hashA1 == hashB1 && hashA2 == hashB2 )
poz [ ++ nrSol ] = 0;
for( i = NA ; i < NB ; ++i )
{
hashB1 = ( ( hashB1 - ( B[ i - NA ] * P1 ) % MOD1 + MOD1 ) * P + B[ i ] ) % MOD1;
hashB2 = ( ( hashB2 - ( B[ i - NA ] * P2 ) % MOD2 + MOD2 ) * P + B[ i ] ) % MOD2;
if( hashA1 == hashB1 && hashA2 == hashB2)
{
nrSol ++;
if( nrSol <= 1000 )
poz[ nrSol ] = i - NA +1 ;
}
}
cout << nrSol << "\n";
if( nrSol <= 1000 )
for( i = 1; i <= nrSol ; i++)
cout << poz[ i ] << " ";
else
for( i = 1; i <= 1000 ; i++)
cout << poz[ i ] << " ";
fclose(stdin);
fclose(stdout);
return 0;
}