Pagini recente » Cod sursa (job #1335381) | Cod sursa (job #831112) | Cod sursa (job #1762596) | Cod sursa (job #1144431)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int NMAX = 2000000;
const int MOD = 666013;
const int base = 27;
vector <int> H[ MOD ], R;
string S, A;
int lg, ind_sol, nr_sol;
int putere( int a, int p) {
int R= 1;
while( p != 0 ) {
if( p%2 == 1 ) {
R= (R*a) % MOD;
}
p>>= 1;
a= (a*a) % MOD;
}
return R;
}
int main()
{
in >> A >> S;
if( A.size() <= S.size() ) {
lg= A.size();
int key= 0, k= 0;
for( int i= 0; i<lg; ++i ) {
int nr1= (int)A[i]-'A'+1;
int nr2= (int)S[i]-'A'+1;
key= ( key + nr1*putere(base , lg-i-1)%MOD ) % MOD;
k= ( k + nr2*putere(base , lg-i-1)%MOD ) % MOD;
}
if( k == key ) {
R.push_back( ind_sol );
}
ind_sol++;
int SCADE= putere(base , A.size()-1);
for( int i= lg; i<(int)S.size(); ++i, ++ind_sol ) {
int nr1= (int)S[i-lg]-'A'+1;
int nr2= (int)S[i]-'A'+1;
k= ((k-( nr1*SCADE % MOD ) ) * base%MOD + nr2) % MOD;
if( k == key ) {
R.push_back( ind_sol );
}
}
out << R.size() << '\n';
for( int i= 0; i<1000 && i<(int)R.size(); ++i ) {
out << R[i] << ' ';
}
out << '\n';
}
else out << 0 << '\n';
return 0;
}