用python3编程解题国王有一个魔镜,可以把任何接触镜面的东西变成原来的两倍——只是,因为是镜子嘛,增加的那部分是反的。 比如一条项链,我们用AB来表示,不同的字母表示不同颜色的珍珠。如果把B端接触镜面的话,魔镜会把这条项链变为ABBA。如果再用一端接触的话,则会变成ABBAABBA(假定国王只用项链的某一端接触魔镜)。 给定最终的项链,请编写程序输出国王没使用魔镜之前,最初的项链可能的最小长度。 输入 第一行是一个整数N(N<=10)表示测试数据的组数) 每组测试数据占一行 只有一个字符串(长度小于100),由大写英文字母组成,表示最终的项链。 输出 每组测试数据的输出只有一个整数,表示国王没使用魔镜前,最初的项链可能的最小长度。
时间: 2024-03-11 15:44:08 浏览: 41
这道题可以使用“双倍经验”的思想,对于给定的项链,我们从最后一位开始遍历,如果这一位是反向的,则我们需要把这一位的前一位也加入到结果中,因为这一位实际上是和前一位重合的。如果这一位是正向的,则我们只需要加入这一位。
最后,我们得到的结果需要除以2,因为我们遍历了整个项链,而实际上我们只需要遍历一半,所以最终的长度是原长度的一半。
下面是Python代码实现:
```python
def find_min_len(chain):
n = len(chain)
for i in range(n - 1, -1, -1):
if chain[i] == chain[0]:
if chain[:n-i] == chain[i:]:
return n - i
return n
t = int(input())
for i in range(t):
chain = input().strip()
print(find_min_len(chain) // 2)
```
这里我们定义了一个`find_min_len`函数来计算最小长度,然后在主程序中读取输入,分别计算每组数据的答案并输出。