這題和 UVa 455 幾乎一模一樣，但測資大上了不少，若暴力破解可能會逾時，需要更有效率的演算法。想像一個字串 abcabcabc。我們可以將它寫兩遍，成為 abcabcabcabcabcabc。此時，原字串便會如下圖成為新字串的 substring，其間隔便是周期。一般會實作 KMP (Link 0 Link 2)，但此題用 strstr 即能達到不錯的效果。（GCC strstr 實作似乎使用 Two Way Algorithm (En))
This problem is almost identical to UVa 455, albeit with a bigger input. Thus, it might timeout if you simply do brute force, and we need a more efficient algorithm. Imagine a repeating string abcabcabc. We can repeat it after itself, making abcabcabcabcabcabc. Now, as the graph below shows, the original string becomes a substring of the new string, and the intervals are equal to the repetition period. Normally, KMP is used, but in this case, strstr works quite well too. (The GCC strstr implementation seems to utilize Two Way Algorithm)
abcabcabcabcabcabc
abcabcabc
abcabcabc
abcabcabc
abcabcabc
UVa Link
#include <iostream>
#include <cstring>
char str[1000001];
char str2[2000002];
int main() {
std::cin.tie(0);
std::ios_base::sync_with_stdio(0);
while (std::cin >> str && str[0] != '.') {
int len = strlen(str);
sprintf(str2, "%s%s", str + 1, str);
char *search = strstr(str2, str);
int period = search - str2;
std::cout << len / (period + 1) << '\n';
}
}