Pagini recente » Cod sursa (job #1739822) | Cod sursa (job #1110391) | Cod sursa (job #1261032) | Cod sursa (job #1422141) | Cod sursa (job #3184384)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
typedef long long ll;
const ll P = 1007, MOD = 1e9 + 7;
int main() {
string a, b;
f >> a >> b;
if (a.size() > b.size()) {
g << "0\n";
exit(0);
}
vector<ll> h(b.size() + 1), putere(b.size() + 1);
vector<int> rez;
rez.reserve(1000);
putere[0] = 1;
for (int i = 0; i < b.size(); ++i) {
putere[i + 1] = (putere[i] * P) % MOD;
h[i + 1] = (h[i] + (b[i] + 1) * putere[i]) % MOD;
}
ll hashul = 0, cnt = 0;
for (int i = 0; i < a.size(); ++i)
hashul = (hashul + (a[i] + 1) * putere[i]) % MOD;
for (int i = 0; i + a.size() - 1 < b.size(); ++i) {
ll curr = (h[i + a.size()] + MOD - h[i]) % MOD;
if (curr == (hashul * putere[i]) % MOD) {
++cnt;
if (rez.size() < 1000)
rez.emplace_back(i);
}
}
g << cnt << "\n";
for (auto it: rez)
g << it << " ";
g << "\n";
}