Pagini recente » Cod sursa (job #916099) | Istoria paginii runda/tot-oni-2012-ziua1-11-12/clasament | Cod sursa (job #1059849) | Statistici Crisan Mihai (yggar) | Cod sursa (job #1691709)
#include<fstream>
#include<cstring>
#define P 73
#define MOD1 100023
#define MOD2 100071
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int NA, NB, HashA1, HashA2, HashB1, HashB2, P1, P2, nr;
char A[2000005], B[2000005], f[2000005];
int main(){
fin >> A;
fin >> B;
NA = strlen( A );
NB = strlen( B );
if( NA > NB ){
fout << 0;
return 0;
}
P1 = P2 = 1;
for( int i = 0; i < NA; i++ ){
HashA1 = ( HashA1 * P + A[i] ) % MOD1;
HashA2 = ( HashA2 * P + A[i] ) % MOD2;
HashB1 = ( HashB1 * P + B[i] ) % MOD1;
HashB2 = ( HashB2 * P + B[i] ) % MOD2;
if( i != 0 ){
P1 = P1 * P % MOD1;
P2 = P2 * P % MOD2;
}
}
nr = 0;
if( HashA1 == HashB1 && HashA2 == HashB2 ){
f[0] = 1;
nr++;
}
for( int i = NA; i < NB; i++ ){
HashB1 = ( ( HashB1 - P1 * B[i - NA] % MOD1 + MOD1 ) * P + B[i] ) % MOD1;
HashB2 = ( ( HashB2 - P2 * B[i - NA] % MOD2 + MOD2 ) * P + B[i] ) % MOD2;
if( HashA1 == HashB1 && HashA2 == HashB2 ){
f[ i - NA + 1 ] = 1;
nr++;
}
}
fout << nr << "\n";
nr = 0;
for( int i = 0; i < NB && nr < 1000; i++ ){
if( f[i] == 1 ){
fout << i << " ";
nr++;
}
}
return 0;
}