-
Notifications
You must be signed in to change notification settings - Fork 34
/
Copy pathE.cpp
53 lines (42 loc) · 949 Bytes
/
E.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
using namespace std;
vector<int> zFunction(const string& s) {
size_t n = s.size();
vector<int> z(n);
z[0] = 0;
int left = 0;
int right = 0;
for (int i = 1; i < n; ++i) {
if (i <= right) {
z[i] = min(right - i + 1, z[i - left]);
}
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
if (i + z[i] - 1 > right) {
left = i;
right = i + z[i] - 1;
}
}
return z;
}
int findLengthOfPeriod(const string& s) {
size_t n = s.size();
vector<int> z = zFunction(s);
int period = n;
for (int i = 1; i < n; ++i) {
if (n % i == 0 && z[i] == n - i) {
period = i;
break;
}
}
return period;
}
int main() {
ios_base::sync_with_stdio(false);
string s;
cin >> s;
cout << findLengthOfPeriod(s);
return 0;
}