finding_borders_1732.cpp (539B)
1 #include <algorithm> 2 #include <iostream> 3 #include <string> 4 #include <vector> 5 6 int main() { 7 std::string s; 8 std::cin >> s; 9 std::vector<size_t> z(s.size(), 0), c; 10 z[0] = s.size(); 11 for (size_t i = 1, j = 0, k = 0; i < s.size(); i++) { 12 if (j < i || z[i-k] == j-i) { 13 for (j = std::max(i, j); j < s.size() && s[j] == s[j-i]; j++) ; 14 z[k=i] = j-i; 15 } else z[i] = std::min(z[i-k], j-i); 16 if (z[i] == s.size()-i) 17 c.push_back(z[i]); 18 } 19 std::sort(c.begin(), c.end()); 20 for (auto x : c) 21 std::cout << x << " "; 22 std::cout << "\n"; 23 }