首页 > 试题广场 >

最小循环节

[编程题]最小循环节
  • 热度指数：3960 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 512M，其他语言1024M
  • 算法知识视频讲解
\hspace{15pt}给定一个长度为 n 、由大小写字母混合构成的字符串 s，你可以无限次的往字符串的任何地方插入任意字符。求新字符串 s 的最小循环节。

\hspace{15pt}对于字符串 b ，找到最短长度的子串 a ，使得字符串 b 是由子串 a 拼接若干次得到的，即 b=aa \cdots a 。这里的子串 a 的长度即为字符串 b 的最小循环节。

输入描述:
\hspace{15pt}在一行上输入一个长度不超过 10^5 、由大小写字母混合构成的字符串 s ，代表初始字符串。


输出描述:
\hspace{15pt}在一行上输出一个整数，代表字符串 s 的最小循环节的长度。
示例1

输入

abcabcD

输出

4

说明

\hspace{15pt}在字符串 \texttt{ 中，最小循环节为 \texttt{ ，其长度为 4 。
算法知识视频讲解
添加回答
Python3
覃亦语头像 覃亦语
# 因为可以插入任何字符，所以最小循环节为原始字符串拥有的那些字符，所以最小循环节的长度就是原有字符串去重后的长度
s = input()
print(len(set(s)))
发表于 2025-03-14 16:57:05 回复(3)
Python3
一份小薯条头像 一份小薯条
既然可以任意插入字符，那么最小循环节必由初始字符串原有的那些字符组成（因为如果我们再加入新的字符，会将循环节扩大），又要确保循环节覆盖到每一个已有字符，所以最小循环节的长度就等于已有字符串去重之后的长度。

s=input()
li=[]
for i in s:
    if i not in li:
        li.append(i)
print(len(li))
发表于 2025-03-13 18:16:52 回复(0)
提交观点

问题信息

哈希
难度：
2条回答 595浏览

热门推荐

相关试题

最小循环节

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号