#include using namespace std; #include #include #include #include #include #include #include #include #if defined(__unix__) || defined(__APPLE__) #include #endif template std::istream& operator>>(std::istream& is, std::vector& v); template std::istream& operator>>(std::istream& is, std::pair& p); template std::istream& operator>>(std::istream& is, std::tuple& t); namespace input_detail { #ifdef LOCAL inline std::size_t& read_count() { static std::size_t count = 0; return count; } inline bool& failed_read() { static bool failed = false; return failed; } inline bool stdin_is_terminal() { #if defined(__unix__) || defined(__APPLE__) return isatty(fileno(stdin)); #else return false; #endif } struct EndOfInputChecker { ~EndOfInputChecker() { if (stdin_is_terminal() || failed_read() || std::cin.bad()) return; std::cin >> std::ws; std::string token; if (std::cin >> token) { std::cerr << "[input error] 入力が余っています。\n" << " 最初に余った値: " << token << '\n' << " N と M、H と W、辺数 m、配列長 n などを間違えていないか確認してください。\n"; std::abort(); } } }; inline void ensure_end_checker() { static EndOfInputChecker checker; (void)checker; } inline void begin_input() { ensure_end_checker(); } template void read_one(std::istream& is, T& value) { if (&is != &std::cin) { is >> value; return; } ensure_end_checker(); ++read_count(); if (!(is >> value)) { failed_read() = true; std::cerr << "[input error] 入力が足りないか、型が合いません。\n" << " " << read_count() << " 個目の値を読み込めませんでした。\n" << " N と M、H と W、辺数 m、配列長 n などを間違えていないか確認してください。\n"; std::abort(); } } #else inline void begin_input() { } template void read_one(std::istream& is, T& value) { is >> value; } #endif template void read_values(Args&... args) { (read_one(std::cin, args), ...); } } struct FastIO { FastIO() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); } }; inline FastIO fast_io_init; template std::istream& operator>>(std::istream& is, std::pair& p) { input_detail::read_one(is, p.first); input_detail::read_one(is, p.second); return is; } template void read_tuple_impl(std::istream& is, Tuple& t, std::index_sequence) { (..., input_detail::read_one(is, std::get(t))); } template std::istream& operator>>(std::istream& is, std::tuple& t) { read_tuple_impl(is, t, std::index_sequence_for{}); return is; } template std::istream& operator>>(std::istream& is, std::vector& v) { for (auto& elem : v) { input_detail::read_one(is, elem); } return is; } template struct is_pair : std::false_type {}; template struct is_pair> : std::true_type {}; template struct is_tuple : std::false_type {}; template struct is_tuple> : std::true_type {}; template struct is_vector : std::false_type {}; template struct is_vector> : std::true_type {}; template void adjust_zero_indexed(T& val) { using DecayedT = std::decay_t; if constexpr (is_pair::value) { adjust_zero_indexed(val.first); adjust_zero_indexed(val.second); } else if constexpr (is_tuple::value) { std::apply([](auto&... args) { (adjust_zero_indexed(args), ...); }, val); } else if constexpr (is_vector::value) { for (auto& elem : val) { adjust_zero_indexed(elem); } } else if constexpr (std::is_arithmetic_v && !std::is_same_v && !std::is_same_v && !std::is_same_v && !std::is_same_v && #if defined(__cpp_char8_t) !std::is_same_v && #endif !std::is_same_v && !std::is_same_v && !std::is_same_v) { --val; } else { } } using default_type = long; template void read(Args&... args) { input_detail::read_values(args...); } template T read_val() { T val; input_detail::read_one(std::cin, val); return val; } template std::pair read_pair() { std::pair p; input_detail::begin_input(); std::cin >> p; return p; } template std::tuple read_tuple() { std::tuple t; input_detail::begin_input(); std::cin >> t; return t; } template && !std::is_same_v, int> = 0> std::vector read_vec(Size n, bool zero_indexed = false) { std::vector v(n); input_detail::begin_input(); std::cin >> v; if (zero_indexed) { adjust_zero_indexed(v); } return v; } template std::vector read_vec(bool zero_indexed = false) { int n; input_detail::read_one(std::cin, n); return read_vec(n, zero_indexed); } template && !std::is_same_v, int> = 0> std::vector> read_vec_pair(Size n, bool zero_indexed = false) { return read_vec>(n, zero_indexed); } template std::vector> read_vec_pair(bool zero_indexed = false) { int n; input_detail::read_one(std::cin, n); return read_vec_pair(n, zero_indexed); } template && !std::is_same_v, int> = 0> std::vector> read_vec_tuple(Size n, bool zero_indexed = false) { return read_vec>(n, zero_indexed); } template std::vector> read_vec_tuple(bool zero_indexed = false) { int n; input_detail::read_one(std::cin, n); return read_vec_tuple(n, zero_indexed); } template std::vector> read_vec_grid(int h, int w, bool zero_indexed = false) { std::vector> grid(h, std::vector(w)); input_detail::begin_input(); std::cin >> grid; if (zero_indexed) { adjust_zero_indexed(grid); } return grid; } template std::vector> read_vec_grid(bool zero_indexed = false) { int h, w; input_detail::read_values(h, w); return read_vec_grid(h, w, zero_indexed); } template && !std::is_same_v, int> = 0> std::vector> read_vec_var(Size n, bool zero_indexed = false) { std::vector> res(n); input_detail::begin_input(); for (int i = 0; i < static_cast(n); ++i) { int m; input_detail::read_one(std::cin, m); res[i] = read_vec(m, zero_indexed); } return res; } template std::vector> read_vec_var(bool zero_indexed = false) { int n; input_detail::read_one(std::cin, n); return read_vec_var(n, zero_indexed); } template T read_zero_idx() { T val; input_detail::read_one(std::cin, val); adjust_zero_indexed(val); return val; } inline std::vector> read_graph(int n, int m, bool directed = false) { std::vector> g(n); input_detail::begin_input(); for (int i = 0; i < m; ++i) { int u = read_zero_idx(); int v = read_zero_idx(); g[u].push_back(v); if (!directed) { g[v].push_back(u); } } return g; } inline std::vector> read_graph(bool directed = false) { int n, m; input_detail::read_values(n, m); return read_graph(n, m, directed); } template struct Edge { int to; Cost cost; Edge() = default; Edge(int to, Cost cost) : to(to), cost(cost) {} }; template inline std::vector>> read_weighted_graph(int n, int m, bool directed = false) { std::vector>> g(n); input_detail::begin_input(); for (int i = 0; i < m; ++i) { int u = read_zero_idx(); int v = read_zero_idx(); Cost w; input_detail::read_one(std::cin, w); g[u].push_back(Edge{v, w}); if (!directed) { g[v].push_back(Edge{u, w}); } } return g; } template inline std::vector>> read_weighted_graph(bool directed = false) { int n, m; input_detail::read_values(n, m); return read_weighted_graph(n, m, directed); } #include #include #include #include #include #include #include #include #include namespace output_detail { template struct is_string_like { private: using U = std::remove_cvref_t; static constexpr bool is_char_array = std::is_array_v && std::is_same_v>, char>; static constexpr bool is_char_pointer = std::is_pointer_v && std::is_same_v>, char>; public: static constexpr bool value = std::is_same_v || std::is_same_v || is_char_array || is_char_pointer; }; template inline constexpr bool is_string_like_v = is_string_like::value; template struct is_iterable : std::false_type {}; template struct is_iterable())), decltype(std::end(std::declval()))>> : std::bool_constant> {}; template inline constexpr bool is_iterable_v = is_iterable::value; } template struct Plus1Wrapper { const T& val; }; namespace output_detail { template struct is_plus1_supported : std::false_type {}; template struct is_plus1_supported< T, std::enable_if_t> && !std::is_same_v, bool> && !std::is_same_v, char> && !std::is_same_v, signed char> && !std::is_same_v, unsigned char> && !std::is_same_v, wchar_t> && #if defined(__cpp_char8_t) !std::is_same_v, char8_t> && #endif !std::is_same_v, char16_t> && !std::is_same_v, char32_t>>> : std::true_type { }; template struct is_plus1_supported> : std::bool_constant::value && is_plus1_supported::value> {}; template struct is_plus1_supported> : std::bool_constant<(is_plus1_supported::value && ...)> {}; template struct is_plus1_supported())), decltype(std::end(std::declval())), decltype(*std::begin(std::declval()))>> : std::bool_constant && is_plus1_supported()))>>::value> {}; template inline constexpr bool is_plus1_supported_v = is_plus1_supported>::value; } template requires output_detail::is_plus1_supported_v constexpr Plus1Wrapper plus1(const T& x) { return Plus1Wrapper{x}; } template void print_val(const T& val); template void print_val(const std::pair& p); template void print_val(const std::tuple& t); template void print_val(const std::optional& opt); template void print_val(const Plus1Wrapper>& w); template void print_val(const Plus1Wrapper>& w); template void print_val(const Plus1Wrapper& w); namespace output_detail { template void print_separated(Func&& print_one, const Args&... args) { bool first = true; auto emit = [&](const auto& x) { if (!first) { std::print(" "); } first = false; print_one(x); }; (emit(args), ...); } } template void print_val(const T& val) { if constexpr (output_detail::is_iterable_v) { bool first = true; for (const auto& item : val) { if (!first) { std::print(" "); } first = false; print_val(item); } } else { std::print("{}", val); } } template void print_val(const std::pair& p) { print_val(p.first); std::print(" "); print_val(p.second); } namespace output_detail { template void print_tuple_impl(const Tuple& t, std::index_sequence) { print_separated([](const auto& x) { print_val(x); }, std::get(t)...); } } template void print_val(const std::tuple& t) { output_detail::print_tuple_impl(t, std::index_sequence_for{}); } template void print_val(const std::optional& opt) { if (opt.has_value()) { print_val(*opt); } else { std::print("-1"); } } template void print_val(const Plus1Wrapper>& w) { print_val(plus1(w.val.first)); std::print(" "); print_val(plus1(w.val.second)); } namespace output_detail { template void print_plus1_tuple_impl(const Tuple& t, std::index_sequence) { print_separated([](const auto& x) { print_val(plus1(x)); }, std::get(t)...); } } template void print_val(const Plus1Wrapper>& w) { output_detail::print_plus1_tuple_impl(w.val, std::index_sequence_for{}); } template void print_val(const Plus1Wrapper& w) { if constexpr (output_detail::is_iterable_v) { bool first = true; for (const auto& item : w.val) { if (!first) { std::print(" "); } first = false; print_val(plus1(item)); } } else { print_val(w.val + 1); } } template void out_1indexed(const Container& c) { auto it = std::begin(c); if (it != std::end(c)) { ++it; } bool first = true; for (; it != std::end(c); ++it) { if (!first) { std::print(" "); } first = false; print_val(*it); } std::println(); } template void out_from1(const Container& c) { out_1indexed(c); } inline void out() { std::println(); } template void out(const Args&... args) { output_detail::print_separated([](const auto& x) { print_val(x); }, args...); std::println(); } template void pr(const Args&... args) { out(args...); } template void out_lines(const Container& c) { for (const auto& x : c) { print_val(x); std::println(); } } template void out_grid(const Grid& grid) { for (const auto& row : grid) { out(row); } } inline void Yes(bool condition = true, std::string_view true_str = "Yes", std::string_view false_str = "No") { std::println("{}", condition ? true_str : false_str); } inline void No(bool condition = true) { Yes(!condition); } #include #include #include #include #include #define ALL(a) (a).begin(), (a).end() using i128 = __int128; template inline bool chmin(T& a, const U& b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T& a, const U& b) { if (a < b) { a = b; return true; } return false; } template inline T div_ceil(T a, T b) { if (a > 0) return a / b + (a % b != 0); return a / b; } template inline T div_floor(T a, T b) { if (a < 0) return a / b - (a % b != 0); return a / b; } template inline T mod(T a, T m) { a %= m; if (a < 0) a += m; return a; } template inline constexpr T INF = std::numeric_limits::max() / 2; template <> inline constexpr float INF = std::numeric_limits::infinity(); template <> inline constexpr double INF = std::numeric_limits::infinity(); template <> inline constexpr long double INF = std::numeric_limits::infinity(); template auto make_vector(size_t size, T&& initial_value) { return std::vector>(size, std::forward(initial_value)); } template auto make_vector(size_t size, Args&&... args) { auto inner = make_vector(std::forward(args)...); return std::vector(size, inner); } template inline std::vector iota_vec(int n, T start = 0) { std::vector v(n); std::iota(v.begin(), v.end(), start); return v; } template inline std::vector doubled_vec(const std::vector& v) { std::vector res; res.reserve(v.size() * 2); res.insert(res.end(), v.begin(), v.end()); res.insert(res.end(), v.begin(), v.end()); return res; } inline bool is_palindrome(std::string_view s) { return std::ranges::equal(s, s | std::views::reverse); } #ifdef LOCAL #include #else #define debug(...) #endif #include #include #include struct KMP { template requires std::ranges::sized_range static std::vector build_mp(const Seq& s) { const int n = static_cast(std::ranges::size(s)); std::vector mp(n + 1); mp[0] = -1; int j = -1; for (int i = 0; i < n; i++) { while (j >= 0 && s[i] != s[j]) j = mp[j]; j++; mp[i + 1] = j; } return mp; } template requires std::ranges::sized_range && std::ranges::sized_range && std::equality_comparable_with, std::ranges::range_reference_t> static std::vector search(const Text& text, const Pattern& pattern) { std::vector result; if (std::ranges::empty(pattern)) return result; std::vector mp = build_mp(pattern); const int n = static_cast(std::ranges::size(text)); const int m = static_cast(std::ranges::size(pattern)); int j = 0; for (int i = 0; i < n; i++) { while (j >= 0 && text[i] != pattern[j]) j = mp[j]; j++; if (j == m) { result.push_back(i - m + 1); j = mp[j]; } } return result; } template requires std::ranges::sized_range && std::ranges::sized_range && std::equality_comparable_with, std::ranges::range_reference_t> static std::vector search_non_overlapping(const Text& text, const Pattern& pattern) { std::vector result; if (std::ranges::empty(pattern)) return result; std::vector mp = build_mp(pattern); const int n = static_cast(std::ranges::size(text)); const int m = static_cast(std::ranges::size(pattern)); int j = 0; for (int i = 0; i < n; i++) { while (j >= 0 && text[i] != pattern[j]) j = mp[j]; j++; if (j == m) { result.push_back(i - m + 1); j = 0; } } return result; } template requires std::ranges::sized_range && std::ranges::sized_range && std::equality_comparable_with, std::ranges::range_reference_t> static std::vector find_all(const Text& text, const Pattern& pattern) { return search(text, pattern); } }; void solve() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; string S; read(N, S); int ans = 0; string&& tmp = S.substr(N - 5, N); string HAPPY = "HAPPY"; for (auto&& [a, b] : ranges::views::zip(tmp, HAPPY)) { ans += a != b; } S[N - 5] = '#'; vector res = KMP::search(S, HAPPY); println("{}", ans + ssize(res)); } int main() { solve(); }