#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"
int32_t size_pattern;
int32_t size_text;
int32_t k;
constexpr int32_t kMod = 1e9 + 7;
std::unordered_map<int32_t, int32_t> mp;
std::string s;
std::vector<int64_t> ans;
std::vector<int64_t> less;
std::vector<int64_t> greater;
bool Ok(const std::vector<int32_t>& s, ll j, ll i) {
if (i >= less.size()) {
return false;
}
ll ind_less = less[i] == -1 ? -1 : j - (i - less[i]);
ll ind_greater = greater[i] == -1 ? -1 : j - (i - greater[i]);
return (j > size_pattern) && ((ind_less == -1 || s[ind_less] < s[j]) &&
(ind_greater == -1 || s[ind_greater] > s[j]));
}
void z_function(const std::vector<int32_t>& s) {
int64_t s_size = s.size();
std::vector<int64_t> z(s_size, 0);
int64_t l = 0;
int64_t r = 0;
for (int64_t i = 1; i < s_size; ++i) {
if (i > r) {
int64_t k = 0, j = 0;
while (i + k < s_size && Ok(s, i + k, j + k)) {
++k;
}
l = i;
r = i + k - 1;
z[i] = k;
continue;
}
z[i] = std::min(r - i + 1, z[i - l]);
int64_t j = 0;
while (i + z[i] < s_size && Ok(s, i + z[i], j + z[i])) {
++z[i];
}
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
// for (int64_t i = 0; i < s.size(); ++i) {
// std::cout << s[i] << " ";
// }
// std::cout << std::endl;
for (int64_t i = 0; i < z.size(); ++i) {
// std::cout << z[i] << " ";
if (z[i] == size_pattern) {
ans.push_back(i - size_pattern);
}
}
// std::cout << std::endl;
}
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);
std::cin >> size_pattern >> size_text;
std::vector<int32_t> pattern(size_pattern);
for (int32_t i = 0; i < size_pattern; ++i) {
int32_t x;
std::cin >> x;
pattern[x - 1] = i + 1;
}
less.resize(size_pattern, -1);
greater.resize(size_pattern, -1);
for (int32_t i = 1; i < size_pattern; ++i) {
if (pattern[i - 1] > pattern[i]) {
ll ind = i - 1;
while (less[ind] != -1 && pattern[less[ind]] > pattern[i]) {
ind = less[ind];
}
greater[i] = ind;
less[i] = less[ind];
} else {
ll ind = i - 1;
while (greater[ind] != -1 && pattern[greater[ind]] < pattern[i]) {
ind = greater[ind];
}
less[i] = ind;
greater[i] = greater[ind];
}
}
std::vector<int32_t> text(size_text);
for (int32_t i = 0; i < size_text; ++i) {
std::cin >> text[i];
}
auto kmp = pattern;
kmp.push_back(0);
for (auto num : text) {
kmp.push_back(num);
}
z_function(kmp);
std::cout << ans.size() << "\n";
for (auto x : ans) {
std::cout << x << " ";
}
}
# | 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... |