#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pk pop_back
#define yes std::cout << "YES\n"
#define no std::cout << "NO\n"
ll size_pattern;
ll size_text;
ll k;
constexpr ll kMod = 1e9 + 7;
std::unordered_map<ll, ll> mp;
std::string s;
constexpr ll kBase = 37;
std::vector<ll> pows(1'000'005);
std::vector<std::pair<ll, ll>> tree((1 << 21) + 5);
void Update(const ll position, const ll value, const ll cur_ind = 1,
const ll left = 1, const ll right = size_text) {
if (left > position || right < position) {
return;
}
if (left == right) {
tree[cur_ind] = {value, value != 0};
// value == 0 только если мы удаляем это число
return;
}
ll mid = (left + right) >> 1;
Update(position, value, cur_ind * 2, left, mid);
Update(position, value, cur_ind * 2 + 1, mid + 1, right);
tree[cur_ind].second =
tree[cur_ind * 2].second + tree[cur_ind * 2 + 1].second;
tree[cur_ind].first =
(tree[cur_ind * 2].first * pows[tree[cur_ind * 2 + 1].second] % kMod +
tree[cur_ind * 2 + 1].first) %
kMod;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
pows[0] = 1;
for (ll i = 1; i <= 1000005; i++) {
pows[i] = (pows[i - 1] * kBase) % kMod;
}
std::cin >> size_pattern >> size_text;
std::vector<ll> pattern(size_pattern);
ll hash_to_add{};
ll need_hash{};
for (ll i = 0; i < size_pattern; ++i) {
std::cin >> pattern[i];
hash_to_add += pows[i];
need_hash = (need_hash * kBase + pattern[i]) % kMod;
hash_to_add %= kMod;
}
std::vector<std::pair<ll, ll>> for_compress(size_text);
for (ll i = 0; i < size_text; ++i) {
std::cin >> for_compress[i].first;
for_compress[i].second = i;
}
std::ranges::sort(for_compress);
std::vector<ll> text(size_text);
for (ll i = 0; i < size_text; ++i) {
text[for_compress[i].second] = i + 1;
}
for (ll i = 0; i < size_pattern; ++i) {
Update(text[i], i + 1);
}
std::vector<ll> ans;
for (ll i = size_pattern; i < size_text; ++i) {
// std::cout << tree[1].first << " " << need_hash << std::endl;
if (tree[1].first == need_hash) {
ans.push_back(i - size_pattern + 1);
}
Update(text[i - size_pattern], 0);
Update(text[i], i + 1);
need_hash += hash_to_add;
need_hash %= kMod;
}
if (tree[1].first == need_hash) {
ans.push_back(size_text - size_pattern + 1);
}
std::cout << ans.size() << '\n';
for (auto ind : ans) {
std::cout << ind << ' ';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |