Pagini recente » Cod sursa (job #2970951) | Borderou de evaluare (job #2970948) | Cod sursa (job #613348)
Cod sursa(job #613348)
#include <fstream>
#include <cstring>
#define LMAX 2000001
#define B 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
char A[LMAX], S[LMAX];
int LA, LB, HashCt1, HashCt2, HashA1, HashA2, i, Pow1, Pow2, NrSol;
bool OK[LMAX];
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int main()
{
in >> A >> S;
LA = strlen( A );
LB = strlen( S );
if( LA > LB )
{
out << 0 << '\n';
return 0;
}
for( Pow1 = Pow2 = 1, HashA1 = HashA2 = i = 0; i < LA; i++ )
{
HashA1 = ( HashA1 * B + A[i] ) % MOD1;
HashA2 = ( HashA2 * B + A[i] ) % MOD2;
if( i )
{
Pow1 = ( Pow1 * B ) % MOD1;
Pow2 = ( Pow2 * B ) % MOD2;
}
}
for( HashCt1 = HashCt2 = i = 0; i < LA; i++ )
{
HashCt1 = ( HashCt1 * B + S[i] ) % MOD1;
HashCt2 = ( HashCt2 * B + S[i] ) % MOD2;
}
memset( OK, false, sizeof( OK ) );
NrSol = 0;
if( HashCt1 == HashA1 && HashCt2 == HashA2 )
OK[0] = true, ++NrSol;
for( i = LA; i < LB; i++ )
{
HashCt1 = ( ( HashCt1 - (Pow1 * S[i - LA])%MOD1 + MOD1 )*B + S[i] ) % MOD1;
HashCt2 = ( ( HashCt2 - (Pow2 * S[i - LA])%MOD2 + MOD2 )*B + S[i] ) % MOD2;
if( HashCt1 == HashA1 && HashCt2 == HashA2 )
OK[i - LA + 1] = true, ++NrSol;
}
out << NrSol << '\n';
if( NrSol )
{
for( NrSol = i = 0; i < LB && NrSol < 1000; i++ )
if( OK[i] )
out << i << ' ', ++NrSol;
out << '\n';
}
return 0;
}