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/a.out | Bin 0 -> 27192 bytes 08_string_algorithms/finding_borders_1732.cpp | 23 +++++++++ 08_string_algorithms/finding_periods_1733.cpp | 29 +++++++++++ 08_string_algorithms/string_matching_1753.cpp | 32 ++++++++++++ 08_string_algorithms/word_combinations_1731.cpp | 63 ++++++++++++++++++++++++ 5 files changed, 147 insertions(+) create mode 100755 08_string_algorithms/a.out create mode 100644 08_string_algorithms/finding_borders_1732.cpp create mode 100644 08_string_algorithms/finding_periods_1733.cpp create mode 100644 08_string_algorithms/string_matching_1753.cpp create mode 100644 08_string_algorithms/word_combinations_1731.cpp (limited to '08_string_algorithms') diff --git a/08_string_algorithms/a.out b/08_string_algorithms/a.out new file mode 100755 index 0000000..4556b32 Binary files /dev/null and b/08_string_algorithms/a.out differ diff --git a/08_string_algorithms/finding_borders_1732.cpp b/08_string_algorithms/finding_borders_1732.cpp new file mode 100644 index 0000000..d5cbbd4 --- /dev/null +++ b/08_string_algorithms/finding_borders_1732.cpp @@ -0,0 +1,23 @@ +#include +#include +#include +#include + +int main() { + std::string s; + std::cin >> s; + std::vector z(s.size(), 0), c; + 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); + if (z[i] == s.size()-i) + c.push_back(z[i]); + } + std::sort(c.begin(), c.end()); + for (auto x : c) + std::cout << x << " "; + std::cout << "\n"; +} 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"; +} 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"; +} diff --git a/08_string_algorithms/word_combinations_1731.cpp b/08_string_algorithms/word_combinations_1731.cpp new file mode 100644 index 0000000..8a26b91 --- /dev/null +++ b/08_string_algorithms/word_combinations_1731.cpp @@ -0,0 +1,63 @@ +#include +#include +#include +#include +#include + +struct TrieNode { + char c; + size_t d; + bool isend; + std::vector next; + + TrieNode(char x, size_t y) : c{x}, d{y}, isend{false}, next() {} +}; + +void push(std::string_view s, TrieNode& t) { + if (s.empty()) { + t.isend = true; + return; + } + for (auto& u : t.next) { + if (s[0] == u.c) { + push(s.substr(1), u); + return; + } + } + t.next.push_back(TrieNode(s[0], t.d+1)); + push(s.substr(1), t.next.back()); +} + +const TrieNode* next(const TrieNode* w, char c) { + for (size_t i = 0; i < w->next.size(); i++) + if (w->next[i].c == c) + return &w->next[i]; + return nullptr; +} + +int f(std::vector& t, std::string_view s, const TrieNode& d, size_t i) { + static constexpr long long mod = 1e9+7; + + if (t[i] != -1) return t[i]; + + t[i] = 0; + for (const TrieNode* w = &d; w != nullptr; w = next(w, s[w->d])) + if (w->isend) + t[i] = (t[i] + f(t, s.substr(w->d), d, i+w->d)) % mod; + return t[i]; +} + +int main() { + std::string s, u; + size_t k; + std::cin >> s >> k; + TrieNode d('\0', 0); + for (size_t i = 0; i < k; i++) { + std::cin >> u; + push(u, d); + } + + std::vector t(s.size()+1, -1); + t[s.size()] = 1; + std::cout << f(t, s, d, 0) << "\n"; +} -- cgit v1.3