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/finding_periods_1733.cpp | 29 +++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) create mode 100644 08_string_algorithms/finding_periods_1733.cpp (limited to '08_string_algorithms/finding_periods_1733.cpp') diff --git a/08_string_algorithms/finding_periods_1733.cpp b/08_string_algorithms/finding_periods_1733.cpp new file mode 100644 index 0000000..edaa1d1 --- /dev/null +++ b/08_string_algorithms/finding_periods_1733.cpp @@ -0,0 +1,29 @@ +#include +#include +#include +#include + +bool isp(const std::vector& z, size_t k) { + for (size_t i = 0; i*k < z.size(); i++) + if (z[i*k] < std::min(k, z.size()-i*k)) + return false; + return true; +} + +int main() { + std::string s; + std::cin >> s; + std::vector z(s.size(), 0); + z[0] = s.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); + } + + for (size_t i = 1; i <= s.size(); i++) + if (isp(z, i)) + std::cout << i << " "; + std::cout << "\n"; +} -- cgit v1.3