From 96254947699986c59f0dc63d69fd4b76bd3ed43e Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Mon, 6 Jul 2026 19:08:08 +0200 Subject: Initial commit --- 08_string_algorithms/string_matching_1753.cpp | 32 +++++++++++++++++++++++++++ 1 file changed, 32 insertions(+) create mode 100644 08_string_algorithms/string_matching_1753.cpp (limited to '08_string_algorithms/string_matching_1753.cpp') diff --git a/08_string_algorithms/string_matching_1753.cpp b/08_string_algorithms/string_matching_1753.cpp new file mode 100644 index 0000000..148ed03 --- /dev/null +++ b/08_string_algorithms/string_matching_1753.cpp @@ -0,0 +1,32 @@ +#include +#include +#include + +struct S { + std::string w; + std::string t; + + size_t size() const { return w.size() + 1 + t.size(); } + + char operator[](size_t i) const { + if (i < w.size()) return w.at(i); + if (i > w.size()) return t.at(i-w.size()-1); + return '$'; + } +}; + +int main() { + S s; + std::cin >> s.t >> s.w; + size_t c{0}; + std::vector z(s.size(), 0); + z[0] = s.w.size(); + for (size_t i = 1, j = 0, k = 0; i < s.size(); i++) { + if (j < i || z[i-k] == j-i) { + for (j = std::max(i, j); j < s.size() && s[j] == s[j-i]; j++) ; + z[k=i] = j-i; + } else z[i] = std::min(z[i-k], j-i); + c += z[i] == s.w.size(); + } + std::cout << c << "\n"; +} -- cgit v1.3