Pagini recente » Cod sursa (job #1512716) | Cod sursa (job #2030829) | Cod sursa (job #1522324) | Monitorul de evaluare | Cod sursa (job #1909014)
#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 Plen;
int64_t Code(const string &s) {
int64_t res = s[0];
for (int i = 1; i < s.size(); ++i)
res = res * P + s[i];
return res;
}
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) {
return poly[j] - poly[i - 1] * Plen;
}
};
int main() {
string a, b;
fin >> a >> b;
Plen = 1;
for (int i = 1; i <= a.size(); ++i)
Plen *= P;
Sir S2(b);
int64_t need = Code(a);
vector<int>match;
int nrMatches = 0;
for (int i = a.size() - 1; i < b.size(); ++i) {
if (S2.get(i - a.size() + 1, i) == need) {
++nrMatches;
if (nrMatches <= 1000)
match.push_back(i - a.size() + 1);
}
}
fout << nrMatches << '\n';
for (int i = 0; i < match.size(); ++i)
fout << match[i] << ' ';
return 0;
}