48 lines
1.1 KiB
C++
48 lines
1.1 KiB
C++
#include <iostream>
|
|
#include <vector>
|
|
|
|
std::ostream& operator<<(std::ostream& os, const std::vector<int>& vector) {
|
|
for (const auto elem : vector) {
|
|
os << elem << ' ';
|
|
}
|
|
return os;
|
|
}
|
|
|
|
std::vector<int> prefix_function(const std::string& s) {
|
|
std::vector<int> pi(s.size());
|
|
for (int i = 1; i < s.size(); i++) {
|
|
int j = pi[i - 1];
|
|
while (true) {
|
|
if (s[i] == s[j]) {
|
|
pi[i] = j + 1;
|
|
break;
|
|
}
|
|
if (j == 0) {
|
|
pi[i] = 0;
|
|
break;
|
|
}
|
|
j = pi[j - 1];
|
|
}
|
|
}
|
|
return pi;
|
|
}
|
|
|
|
int main() {
|
|
std::ios::sync_with_stdio(false);
|
|
std::cin.tie(nullptr);
|
|
|
|
std::string s;
|
|
while (std::cin >> s && s != ".") {
|
|
auto pi = prefix_function(s);
|
|
std::clog << pi << std::endl;
|
|
int period = static_cast<int>(s.size()) - pi.back();
|
|
if (s.size() % period != 0) {
|
|
std::cout << 1 << std::endl;
|
|
} else {
|
|
std::cout << s.size() / period << std::endl;
|
|
}
|
|
}
|
|
|
|
return 0;
|
|
}
|