Pagini recente » Cod sursa (job #3684) | Cod sursa (job #3220444) | Cod sursa (job #36764) | Cod sursa (job #3251087) | Cod sursa (job #482824)
Cod sursa(job #482824)
#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 hashaa = 0, hashbb = 0;
long long pow_size_a = 1;
long long pow_size_aa = 1;
for (int i = 0; i < a.size(); i++) {
hasha = (131321 * hasha + a[i]) % 100000001;
hashaa = (13131 * hashaa + a[i]) % 10000001;
hashb = (131321 * hashb + b[i]) % 100000001;
hashbb = (13131 * hashbb + b[i]) % 10000001;
pow_size_a = (pow_size_a * 131321) % 100000001;
pow_size_aa= (pow_size_aa * 13131) % 10000001;
}
vector<int> pos;
for (int i = a.size() - 1; i < b.size(); i++) {
if (hasha == hashb && hashaa == hashbb) {
pos.push_back(i - a.size() + 1);
}
if (i != b.size() - 1) {
hashb = (131321 * hashb + b[i + 1]) % 100000001;
hashbb = (13131 * hashbb + b[i + 1]) % 10000001;
hashbb = (hashbb + 256ll * 10000001ll - b[i - a.size() + 1] * pow_size_aa) % 10000001;
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;
}