AcWing 777. 字符串乘方
1. 地址
https://www.acwing.com/problem/content/779/
2. 题解
#include <iostream>
#include <cstdio>
using namespace std;
/*
算法思路：
通过本题性质，我们可以发现：
1. 子串长度*n = 主串长度，既然这里要求最大的n，那么我们可以循环遍历n，看看主串长度能否可以整除n。
2. n的范围最大不超过主串长度，最小就是1，此时子串就等于主串。
3. 找到n之后，根据上述公式，我们可以得到子串长度。
4. 由于主串有多个子串拼接n次得到，那么主串的前子串长度所代表的子串一定跟子串相等。
5. 所以，根据第4点，我们可以根据子串长度取得主串的一部分作为子串。
6. 然后，再让子串拼接n次得到新的主串。
7. 如果新的主串跟原主串相等，那么该子串符合题目要求，n也是最大的。（因为n从大到小遍历）
8. 如果不等，那么子串不符合题目要求，同时n也不符合题目要求。
*/
int main(){
string str;
while(cin >> str, str != "."){
int len = str.size(); //主串长度
//遍历n
for(int n = len; n>=1 ;n--){
if(len % n == 0){
int length = len / n; //子串长度
//取子串
string r = str.substr(0,length);
string new_str = "";
//组合新的主串
for(int i=0;i<n;i++){
new_str += r;
}
if(new_str == str){
cout << n << endl;
break;
}
}
}
}
return 0;
}