Pagini recente » Cod sursa (job #1814531) | Cod sursa (job #72699) | Cod sursa (job #72700) | Borderou de evaluare (job #3335589) | Cod sursa (job #3328376)
#include <fstream>
#include <cstring>
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char A[2000001], B[2000001];
int poz[2000001];
int main()
{
cin >> A;
cin >> B;
int nrca = strlen(A);
int nrcb = strlen(B);
if(nrca > nrcb){
cout << "0\n";
return 0;
}
int nra1 = 0;
int nra2 = 0;
int nrb1 = 0;
int nrb2 = 0;
int p = 1;
int rez = 0;
for(int i = 0; i < nrca; i++){
nra1 += A[i] * 62 * p % MOD1;
nra2 += A[i] * 62 * p % MOD2;
nrb1 += B[i] * 62 * p % MOD1;
nrb2 += B[i] * 62 * p % MOD2;
p *= 62;
}
p /= 62;
for(int i = 0; i <= nrcb - nrca - 1; i++){
if(nra1 == nrb1 && nra2 == nrb2){
poz[++rez] = i;
}
nrb1 = ((nrb1 % MOD1 - (B[i] * p) % MOD1) + MOD1) % MOD1;
nrb1 *= 62;
nrb1 += B[i+nrca];
nrb1 %= MOD1;
nrb2 = ((nrb2 % MOD2 - (B[i] * p) % MOD2) + MOD2) % MOD2;
nrb2 *= 62;
nrb2 += B[i+nrca];
nrb2 %= MOD2;
}
cout << rez << "\n";
for(int i = 1; i <= rez; i++){
cout << poz[i] << " ";
}
cout << "\n";
return 0;
}