原题来自:POJ 2406 给定若干个长度 ≤106 的字符串,询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如:ababab 则最多有 3 个 ab 连接而成。 【输入】 输入若干行,每行有一个字符串,字符串仅含英语字母。特别的,字符串可能为 . 即一个半角句号,此时输入结束。用c++
时间: 2025-06-26 18:25:12 浏览: 18
这是一个经典的字符串处理问题,目标是找出一个字符串可以由多少个相同的子串拼接而成。以下是解决该问题的一种思路,并附上 C++ 示例代码。
### 解决方案
对于这个问题,我们可以通过以下步骤完成:
1. **寻找最短重复单元**
- 如果某个字符串 `s` 可以表示为多次重复某些更小的字串,则这个最小单位一定是一个能够整除原字符串长度的部分。
2. **检查是否满足条件**
- 对于每个可能的分割大小(从 1 开始到字符串长度的一半),尝试将整个字符串按此长度切分并验证所有部分都相等。
3. **终止条件**
- 输入直到遇到字符`.`为止,需要特别注意这是结束标志而非普通数据的一部分。
下面是基于上述思想的具体实现代码示例:
```cpp
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
while (cin >> s && s != ".") { // 终止条件为读取到'.'
int n = s.size();
if(n ==0){
cout << "0" << endl; continue;}
bool flag=false;//用于判断是否存在符合条件的情况
for(int i=1;i<=n&& !flag ;i++)//遍历所有的可能性作为候选周期数
if( n%i==0 ){
bool ok=true;
for(int j=i;j<n;j++)
if(s[j]!=s[j-i]){
ok=false;break;}
if(ok){cout<<(n/i)<<endl;flag=true;}
}
if(!flag)cout<<"1"<<endl;//如果没有任何匹配情况则只能认为自身就是那个唯一的整体
}return 0;}
```
### 程序说明
- 首先逐行接收输入直至遇见特殊字符“.”停止循环;
- 接着对每一个非空有效字符串依据其总长逐步试探哪些因子对应的片段能完美构成原始序列内容本身;
- 最终输出相应的最大次数数值结果或者默认值 '1' 表明不可拆分成更多相同段落形式存在;
阅读全文
相关推荐



















