原题来自:POJ 2406 给定若干个长度 ≤106 的字符串,询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如:ababab 则最多有 3 个 ab 连接而成。 【输入】 输入若干行,每行有一个字符串,字符串仅含英语字母。特别的,字符串可能为 . 即一个半角句号,此时输入结束。
时间: 2025-06-26 18:25:09 浏览: 15
这道题目属于字符串分解的经典问题之一,目的是将一个较长的字符串拆解为尽可能多的完全相同的子串拼接而成的形式。下面是具体的思路解析、代码框架设计以及需要注意的地方。
---
### **核心思想**
我们需要找到一种方法来确定最长的重复单位子串。具体做法可以分为以下几个步骤:
1. 构造一个新的辅助字符串:将原始字符串 `s` 拼接到自身之后形成新的字符串 `t=s+s`, 但是去掉首尾各一位元素得到最终版本`t'=t[1:-1]`.
2. 再利用KMP(Knuth-Morris-Pratt)算法寻找原字符串`s`在新构造出来的字符串`t'`里的最早出现位置index.
3. 根据所得的位置索引 index 计算得出最大可能分割数目k=len(s)//(len(s)-index).
4. 特殊情况考虑,若index等于零表示整个字符串是由单一字符构成,那么直接返回字符串总长度即可.
---
### **详细解释与示例**
举个例子说明一下这个过程:
假设我们的目标字符串S="abcabcabc"
- 第一步生成T='bcabcabca'
然后应用KMP找寻模式串"S"出现在文本串"T'"中的首次位置Index:
| i | T'[i]| prefix length|
|--|------|---------------|
|0 |b | |
|...|.....|...............|
最后发现第一次完整匹配发生在第三个字符开始处(Index=3), 所以我们可以推导出 S 最少由 (Length of String)/(Position)=9/(9-3)=3段相同的部分组成。
---
### **注意事项**
1. 要注意边界条件处理好,特别是当输入只有一个字母或者"."的时候应该怎样合理反馈。
2. 因为涉及大量字符串操作,所以选择合适的数据结构非常重要,在python语言里面推荐使用bytearray而不是普通的string因为前者支持就地修改效率更高;而在C++则可以用vector<char>.
---
### 示例代码(Python版):
``` python
def maxRepeat(s):
if len(set(s)) == 1 or s=='.': return len(s)
t = (s + s)[1:-1]
pi = [0]*len(t)
for i in range(1,len(t)):
j = pi[i-1]
while(j>0 and t[j]!=t[i]):
j=pi[j-1]
if(t[j]==t[i]):j+=1
pi[i]=j
pos = pi[-1]
return int(len(s)/(len(s)-pos))
# Main Function to read multiple lines until '.'
import sys
lines=sys.stdin.readlines()
for line in lines[:-1]:
print(maxRepeat(line.strip()))
```
---
阅读全文
相关推荐

















