Pagini recente » Cod sursa (job #1706461) | Cod sursa (job #554364) | Cod sursa (job #1279844) | Cod sursa (job #2400975) | Cod sursa (job #3334647)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
using namespace std;
string a, b;
#define MOD 50021
#define BAZA 71
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int egale(int poz){
for (int i = 0; i < a.size(); i++){
if (a[i] != b[i + poz]){
return 0;
}
}
return 1;
}
int main()
{
fin >> a >> b;
if (a.size() > b.size()){
fout << "0";
return 0;
}
int hashA = 0, B = 1;
for (int i = 0; i < a.size(); i++){
a[i] -= '0';
hashA = (hashA * BAZA + a[i]) % MOD;
if (i > 0){
B = (B * BAZA) % MOD;
}
}
int hashB = 0;
for (int i = 0; i < b.size(); i++){
b[i] -= '0';
}
for (int i = 0; i < a.size(); i++){
hashB = (hashB * BAZA + b[i]) % MOD;
}
vector <int> rez;
int nr = 0;
if (hashA == hashB && egale(0) == 1){
nr++;
rez.push_back(0);
}
for (int i = a.size(); i < b.size(); i++){
hashB = (((hashB - b[i - a.size()] * B) % MOD + MOD) * BAZA + b[i]) % MOD;
if (hashA == hashB && egale(i - a.size() + 1)){
nr++;
rez.push_back(i - a.size() + 1);
}
}
fout << nr << '\n';
for (int i = 0; i < rez.size(); i++){
fout << rez[i] << " ";
}
return 0;
}