首页 > 试题广场 >

最小循环节

[编程题]最小循环节
  • 热度指数：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()
li=[]
for i in s:
    if i not in li:
        li.append(i)
print(len(li))
发表于 2025-03-13 18:16:52 回复(0)
Python3
覃亦语头像 覃亦语
# 因为可以插入任何字符，所以最小循环节为原始字符串拥有的那些字符，所以最小循环节的长度就是原有字符串去重后的长度
s = input()
print(len(set(s)))
发表于 2025-03-14 16:57:05 回复(3)
Java
牛客281381469号头像 牛客281381469号 
脑筋急转弯题，实际上就是求有多少个不同的字母。
import java.util.Scanner;
import java.util.HashSet;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            HashSet<Character> set = new HashSet<>();
            for (char c : str.toCharArray()){
                set.add(c);
            }
            System.out.println(set.size());
        }
    }
}

发表于 2025-07-18 19:16:31 回复(1)
Java
我好中意你啊头像 我好中意你啊
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String str = in.nextLine();
            Set<Character> set = new HashSet<Character>();
            for (int i = 0; i < str.length(); i++) {
                set.add(str.charAt(i));
            }
            // 不同字符的个数即为最小循环节
            System.out.println(set.size());
        }
    }
}
发表于 2025-03-28 18:02:24 回复(0)
nothing5头像 nothing5
#include <iostream>
#include <set>
using namespace std;

int main() {
    string s;
    cin >> s;
    set<char> li;
    for(auto it : s) {
        li.insert(it);
    }
    cout << li.size();
}
// 64 位输出请用 printf("%lld")
发表于 2025-10-21 21:56:30 回复(0)
在吃瓜的可乐很胆小头像 在吃瓜的可乐很胆小 
print(len(set(input())))

发表于 2025-09-04 15:47:08 回复(0)
1900201910072158499头像 1900201910072158499
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        HashSet<Character> hashSet = new HashSet<>();
        while (in.hasNext()) { // 注意 while 处理多个 case
            String s = in.next();
            char[] chars = s.toCharArray();
            for (char c : chars) {
                hashSet.add(c);
            }
            System.out.println(hashSet.size());
        }
    }
}
发表于 2025-08-21 15:36:43 回复(0)
C
洛篝头像 洛篝
#include <stdio.h>
int main() {
    char c,s[1000],num=0,k=0;
    while(c=getchar(),c!='\n'){
        for(int i=0;i<num;i++){
            if(s[i]==c) k=1;
        }
        if(k==0) {s[num]=c;num++;}
        k=0;
    }
    printf("%d",num);
}
发表于 2025-05-08 21:54:37 回复(0)
牛客482602990号头像 牛客482602990号
print(len(set(list(input()))))
发表于 2025-04-20 12:35:46 回复(0)
Endeavor_1头像 Endeavor_1
set函数直接解决，先给出一个复杂做法 
#include <bits/stdc++.h>
using namespace std;

int main() {
    string str;
    cin >> str;
    set<int> A;
    int a[52];
    memset(a,0,sizeof a);
    for(int i = 0 ; i < str.size() ; i ++){
        if(str[i] >= 'a' && str[i] <= 'z'){
            a[str[i] - 'a']++;
        }
        else if(str[i] >= 'A' && str[i] <= 'Z'){
            a[str[i]-'A' + 26]++;
        }
    }
    int sum = 0;
    for(int i = 0 ; i < 52 ; i++){
        if(a[i] > 0){sum++;}
    }
    cout << sum << endl;
}
set函数做法 
#include <bits/stdc++.h>

using namespace std;

int main() {
    set<char> a;
    string str;
    cin >> str;
    for(int i = 0 ; i < str.size() ; i ++){
        a.insert(str[i]);
    }
    cout << a.size() << endl;

    return 0;
}



发表于 2025-04-13 22:00:34 回复(0)
JavaScript Node
牛客928288679号头像 牛客928288679号
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    // Write your code here
    while ((line = await readline())) {
        let tokens = line.split("");

        const arr = new Set(tokens);
        const _arr = Array.from(arr);
        
        return _arr.length;
    }
})();
发表于 2025-04-04 22:58:18 回复(0)
C
在考古的coder很讲原则头像 在考古的coder很讲原则
#include <stdio.h>
#include<string.h>
int main()
{
    char str[100001];
    int hash[128]={0};
    scanf("%s",str);
    int m=strlen(str);
    for(int i=0;i<m;i++)
    {
        int asc=(int)str[i];
        hash[asc]+=1;
    }
    int sum=0;
    for(int i=0;i<128;i++)
    {
        if(hash[i]>0)
        sum++;
    }
    printf("%d",sum);
}
发表于 2025-03-20 08:53:22 回复(0)
牛客563945260号头像 牛客563945260号 
#include<iostream>
#include<set>
using namespace std;

int main(){
    string s;
    cin>>s;
    set<char> st;
    for(auto&ch:s) st.insert(ch);
    cout<<st.size();
}

发表于 2025-03-13 16:26:38 回复(0)
提交观点

问题信息

哈希
难度：
13条回答 592浏览

热门推荐

相关试题

最小循环节

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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