《蓝桥杯每日一题》KMP算法·AcWing 141. 周期

简介: 《蓝桥杯每日一题》KMP算法·AcWing 141. 周期

1.题目描述


一个字符串的前缀是从第一个字符开始的连续若干个字符,例如 abaab 共有 55 个前缀,分别是 aababaabaaabaab


我们希望知道一个 N 位字符串 S 的前缀是否具有循环节。


换言之,对于每一个从头开始的长度为 i(i>1)的前缀,是否由重复出现的子串 A 组成,即 AAA…A (A 重复出现 K 次,K>1)。


如果存在,请找出最短的循环节对应的 K 值(也就是这个前缀串的所有可能重复节中,最大的 K值)。


输入格式

输入包括多组测试数据,每组测试数据包括两行。


第一行输入字符串 S 的长度 N。


第二行输入字符串 S。


输入数据以只包括一个 0 的行作为结尾。


输出格式


对于每组测试数据,第一行输出 Test case # 和测试数据的编号。

接下来的每一行,输出具有循环节的前缀的长度 i 和其对应 K,中间用一个空格隔开。

前缀长度需要升序排列

在每组测试数据的最后输出一个空行。


数据范围


2≤N≤1000000


输入样例:


3aaa4abcd12aabaabaabaab0


输出样例:


Test case #12 23 3Test case #2Test case #32 26 29 312 4


2.思路解析


不清楚kmp的可以先看下这篇

https://blog.csdn.net/m0_68055637/article/details/128596380


首先发现一个性质,对字符串S自己匹配求出next数组,然后根据定义,对于每一个i,s[i-next[i]+1~i]与s[1~next[i]]是相等的,而且不存在更大的next值满足条件.


既然如此的话,那么我们发现当i-next[i]能够整除i时候,那么s[1~i-next[i]]就是s[i-1]的最小循环元,至于次数那么也就是i/(i-next[i]).


3.代码


import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        num=0;
        while(true){
            int n=sc.nextInt();
            if(n==0){
                break;
            }
            String str1=sc.next();
            num++;
            System.out.println("Test case #"+num);
            shuchu(n,str1);
            System.out.println();
        }
    }
    public static int num;
    public static void shuchu(int n,String str){
        //KMP的next的数组
        int[]next=new int[n];
        //此处next的数组是使用最大长度表实现 跟next[0]=-1意义不同
        next[0]=0;
        for (int i = 1,j=0; i <n ; i++) {
            while(j>0 &&str.charAt(j)!=str.charAt(i)){
                j= next[j-1];
            }
            if(str.charAt(i)==str.charAt(j)){
                j++;
            }
            next[i]=j;
            if(next[i]!=0){
           //i+1是当前字符串的长度 i+1-next[i]是这个字符串重复的子串的长度
                if((i+1)%(i+1-next[i])==0){ 
                    int temp=(i+1)/(i+1-next[i]); //个数
                    System.out.println((i+1)+" "+temp);
                }
            }
        }
    }
}


感谢你能看完, 如有错误欢迎评论指正,有好的思路可以交流一波,如果对你有帮助的话,点个赞支持下

相关文章
|
14天前
|
存储 机器学习/深度学习 算法
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
第十五届蓝桥杯pb组国赛E题[马与象] (15分)BFS算法 详解
17 3
|
1月前
|
算法
数据结构中的KMP算法及其改进算法
KMP算法通过引入部分匹配表,有效避免了重复计算,从而将字符串匹配的时间复杂度降低到O(m+n)。通过进一步优化next数组,KMP算法的效率得到了进一步提升。对于大规模字符串匹配问题,KMP算法及其改进算法提供了高效的解决方案,是计算机科学领域的经典算法之一。
27 3
|
10天前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
12天前
|
人工智能 算法 BI
一篇文章讲明白KMP算法(俗称看毛片算法)
一篇文章讲明白KMP算法(俗称看毛片算法)
13 0
|
15天前
|
存储 人工智能 算法
程序与技术分享:Acwing算法笔记
程序与技术分享:Acwing算法笔记
|
18天前
|
算法 Java
Java数据结构与算法:字符串匹配算法之KMP算法
Java数据结构与算法:字符串匹配算法之KMP算法
|
21天前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
2月前
|
算法
|
1天前
|
算法 数据挖掘
MATLAB数据分析、从算法到实现
MATLAB数据分析、从算法到实现
|
7天前
|
机器学习/深度学习 算法 调度
Matlab|基于改进鲸鱼优化算法的微网系统能量优化管理matlab-源码
基于改进鲸鱼优化算法的微网系统能量管理源码实现,结合LSTM预测可再生能源和负荷,优化微网运行成本与固定成本。方法应用于冷热电联供微网,结果显示经济成本平均降低4.03%,提高经济效益。代码包括数据分段、LSTM网络定义及训练,最终展示了一系列运行结果图表。