Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #2370730) | Borderou de evaluare (job #3349721) | Cod sursa (job #3333277)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
string a, b;
#define MOD1 50021
#define MOD2 50023
#define BAZA 101
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int main()
{
fin >> a >> b;
if (a.size() > b.size()){
cout << "0";
return 0;
}
int hashA1 = 0, hashA2 = 0, B1 = 1, B2 = 1;
for (int i = 0; i < a.size(); i++){
hashA1 = (hashA1 * BAZA + a[i]) % MOD1;
hashA2 = (hashA2 * BAZA + a[i]) % MOD2;
if (i > 0){
B1 = (B1 * BAZA) % MOD1;
B2 = (B2 * BAZA) % MOD2;
}
}
int hashB1 = 0, hashB2 = 0;
for (int i = 0; i < a.size(); i++){
hashB1 = (hashB1 * BAZA + b[i]) % MOD1;
hashB2 = (hashB2 * BAZA + b[i]) % MOD2;
}
vector <int> rez;
int nr = 0;
if (hashA1 == hashB1 && hashA2 == hashB2){
nr++;
rez.push_back(0);
}
for (int i = a.size(); i < b.size(); i++){
hashB1 = (((hashB1 - b[i - a.size()] * B1) % MOD1 + MOD1) * BAZA + b[i]) % MOD1;
hashB2 = (((hashB2 - b[i - a.size()] * B2) % MOD2 + MOD2) * BAZA + b[i]) % MOD2;
if (hashA1 == hashB1 && hashA2 == hashB2){
nr++;
rez.push_back(i - a.size() + 1);
}
}
fout << nr << '\n';
for (int i = 0; i < rez.size(); i++){
fout << rez[i] << " ";
}
return 0;
}