Pagini recente » Rating Cioba Victor (cioba_victor) | Istoria paginii utilizator/wdjpng | Cod sursa (job #2003457) | Cod sursa (job #2604640) | Cod sursa (job #1908992)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int P = 1e9 + 7;
const int nMax = 2e6;
int64_t power[nMax + 2];
void Precalcpower() {
power[0] = 1;
for (int i = 1; i <= nMax; ++i)
power[i] = power[i - 1] * P;
}
struct Sir {
string s;
vector<int64_t>poly;
Sir(const string &s) : s(s) {
poly.resize(s.size());
poly[0] = s[0];
for (int i = 1; i < s.size(); ++i) {
poly[i] = poly[i - 1] * P + s[i];
}
}
int64_t BigHash() {
return poly.back();
}
int64_t get(int i, int j) {
if (i == 0)
return poly[j];
return poly[j] - poly[i - 1] * power[j - i + 1];
}
};
int main() {
string a, b;
fin >> a >> b;
Precalcpower();
Sir S1(a), S2(b);
int64_t need = S1.BigHash();
vector<int>match;
for (int i = a.size() - 1; i < b.size(); ++i) {
if (S2.get(i - a.size() + 1, i) == need)
match.push_back(i - a.size() + 1);
}
fout << match.size() << '\n';
for (int i = 0; i < min(1000, (int)match.size()); ++i)
fout << match[i] << ' ';
return 0;
}