Pagini recente » Cod sursa (job #2499486) | Cod sursa (job #1971037) | Cod sursa (job #2154646) | Cod sursa (job #3154099) | Cod sursa (job #1691387)
#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;
}