finding_periods_1733.cpp (665B)
1 #include <algorithm> 2 #include <iostream> 3 #include <string> 4 #include <vector> 5 6 bool isp(const std::vector<size_t>& z, size_t k) { 7 for (size_t i = 0; i*k < z.size(); i++) 8 if (z[i*k] < std::min(k, z.size()-i*k)) 9 return false; 10 return true; 11 } 12 13 int main() { 14 std::string s; 15 std::cin >> s; 16 std::vector<size_t> z(s.size(), 0); 17 z[0] = s.size(); 18 for (size_t i = 1, j = 0, k = 0; i < s.size(); i++) { 19 if (j < i || z[i-k] == j-i) { 20 for (j = std::max(i, j); j < s.size() && s[j] == s[j-i]; j++) ; 21 z[k=i] = j-i; 22 } else z[i] = std::min(z[i-k], j-i); 23 } 24 25 for (size_t i = 1; i <= s.size(); i++) 26 if (isp(z, i)) 27 std::cout << i << " "; 28 std::cout << "\n"; 29 }