Pagini recente » Cod sursa (job #1396444) | Cod sursa (job #1278892) | Cod sursa (job #2693684) | Cod sursa (job #2095382) | Cod sursa (job #1144442)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int NMAX = 2000000;
const int MOD1 = 666013;
const int MOD2 = 696961;
const int base = 256;
vector <int> R;
string S, A;
int lg, ind_sol, nr_sol;
int main()
{
in >> A >> S;
if( A.size() <= S.size() ) {
lg= A.size();
int k1= 0, k2= 0, h1= 0, h2= 0, p1= 1, p2= 1;
for( int i= 0; i<lg; ++i, p1=(p1*base)%MOD1, p2=(p2*base)%MOD2 ) {
h1= (h1*base+A[i])%MOD1; h2= (h2*base+A[i])%MOD2;
k1= (k1*base+S[i])%MOD1; k2= (k2*base+S[i])%MOD2;
}
p1/= base; p2/= base;
if( k1==h1 && k2==h2 ) {
R.push_back( ind_sol );
++nr_sol;
}
for( int i= lg; i<(int)S.size(); ++i, ++ind_sol ) {
k1= k1-(int)S[i-lg]; k2= k2-(int)S[i-lg];
k1/= p1; k2/= p2;
k1= (k1+p1*(int)S[i])%MOD1; k2= (k2+p2*(int)S[i])%MOD2;
if( k1==h1 && k2==h2 ) {
++nr_sol;
R.push_back( ind_sol );
}
}
out << nr_sol << '\n';
for( int i=0; i<(int)R.size() && i<1000; ++i ) {
out << R[i] << ' ';
}
out << '\n';
}
else out << 0 << '\n';
return 0;
}