5 files changed, 147 insertions, 0 deletions

diff --git a/08_string_algorithms/a.out b/08_string_algorithms/a.out
new file mode 100755
index 0000000..4556b32
--- /dev/null
+++ b/08_string_algorithms/a.out
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 <algorithm>
+#include <iostream>
+#include <string>
+#include <vector>
+
+int main() {
+        std::string s;
+        std::cin >> s;
+        std::vector<size_t> 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 <algorithm>
+#include <iostream>
+#include <string>
+#include <vector>
+
+bool isp(const std::vector<size_t>& 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<size_t> 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 <iostream>
+#include <string>
+#include <vector>
+
+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<size_t> 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 <iostream>
+#include <queue>
+#include <string>
+#include <string_view>
+#include <vector>
+
+struct TrieNode {
+        char c;
+        size_t d;
+        bool isend;
+        std::vector<TrieNode> 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<int>& 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<int> t(s.size()+1, -1);
+        t[s.size()] = 1;
+        std::cout << f(t, s, d, 0) << "\n";
+}