Pagini recente » Cod sursa (job #1407853) | Cod sursa (job #2868735) | Cod sursa (job #2747636) | Cod sursa (job #1429155) | Cod sursa (job #2964180)
#include "bits/stdc++.h"
#include <vector>
using namespace std;
#if defined(ONPC)
#include "bits/debug.h"
#endif
using i64 = long long;
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
class HashedString {
private:
static const int P = 53;
static const int mod = 1e9 + 7;
int N = -1;
vector<int> pw;
vector<int> ha;
int mul(int a, int b) { return (i64) a * b % mod; }
int add(int a, int b) { a += b; if (a >= mod) a -= mod; return a; }
int sub(int a, int b) { a -= b; if (a < 0) a += mod; return a; }
public:
HashedString(const string &s) {
N = (int)s.size();
ha = vector<int>(N + 1);
pw = vector<int>(N + 1);
pw[0] = 1;
for (int i = 0; i < N; ++i) {
ha[i + 1] = add(mul(ha[i], P), (s[i] - 'A' + 1));
pw[i + 1] = mul(pw[i], P);
}
}
int get_hash(const int &l, const int &r) { // [l, r)
return sub(ha[r], mul(ha[l], pw[r - l]));
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
string s, t;
cin >> s >> t;
int n = (int)s.size(), m = (int)t.size();
if (n > m) {
cout << "0\n";
return 0;
}
vector<int> ans;
HashedString h_s(s), h_t(t);
int hs = h_s.get_hash(0, n);
for (int i = 0; i <= m - n; ++i) {
int ht = h_t.get_hash(i, i + n);
if (hs == ht) {
ans.push_back(i);
}
if ((int)ans.size() == 1000) break;
}
cout << (int)ans.size() << "\n";
for (int &x : ans) cout << x << ' ';
cout << "\n";
return 0;
}