网站建设中面包屑导航的特点,wordpress hexo,商标注册官网查询,英文网站建设 招标1.题目描述一个字符串的前缀是从第一个字符开始的连续若干个字符#xff0c;例如 abaab 共有 55 个前缀#xff0c;分别是 a#xff0c;ab#xff0c;aba#xff0c;abaa#xff0c;abaab。我们希望知道一个 N 位字符串 S 的前缀是否具有循环节。换言之#xff0c;对于每…1.题目描述一个字符串的前缀是从第一个字符开始的连续若干个字符例如 abaab 共有 55 个前缀分别是 aababaabaaabaab。我们希望知道一个 N 位字符串 S 的前缀是否具有循环节。换言之对于每一个从头开始的长度为 ii1的前缀是否由重复出现的子串 A 组成即 AAA…A A 重复出现 K 次,K1。如果存在请找出最短的循环节对应的 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 42.思路解析不清楚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 scnew Scanner(System.in);num0;while(true){int nsc.nextInt();if(n0){break;}String str1sc.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[]nextnew int[n];//此处next的数组是使用最大长度表实现 跟next[0]-1意义不同next[0]0;for (int i 1,j0; i n ; i) {while(j0 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){//i1是当前字符串的长度 i1-next[i]是这个字符串重复的子串的长度if((i1)%(i1-next[i])0){ int temp(i1)/(i1-next[i]); //个数System.out.println((i1) temp);}}}}
}
感谢你能看完 如有错误欢迎评论指正有好的思路可以交流一波如果对你有帮助的话点个赞支持下
