Pagini recente » Cod sursa (job #3258039) | Cod sursa (job #3236464) | Cod sursa (job #5389) | Cod sursa (job #3128162) | Cod sursa (job #482822)
Cod sursa(job #482822)
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int main() {
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
fin >> a;
fin >> b;
if (a.size() > b.size()) {
fout << 0 << endl;
}
long long hasha = 0, hashb = 0;
long long pow_size_a = 1;
for (int i = 0; i < a.size(); i++) {
hasha = (131321 * hasha + a[i]) % 100000001;
hashb = (131321 * hashb + b[i]) % 100000001;
pow_size_a = (pow_size_a * 131321) % 100000001;
}
vector<int> pos;
for (int i = a.size() - 1; i < b.size(); i++) {
if (hasha == hashb) {
pos.push_back(i - a.size() + 1);
}
if (i != b.size() - 1) {
hashb = (131321 * hashb + b[i + 1]) % 100000001;
hashb = (hashb + 256ll * 100000001ll - b[i - a.size() + 1] * pow_size_a) % 100000001;
}
}
fout << pos.size() << endl;
for(int i = 0; i < pos.size(); i++) {
fout << pos[i] << " ";
}
fout << endl;
return 0;
}