字符串----HDU-1358
2023-03-14 09:45:22 时间
题目大意:求字符串的前缀是否为周期串,若是,打印出循环节的长度以及循环次数。
这道题考察的是KMP算法中next数组的应用,必须理解透next[]数组代表的含义才t能通过它解决这道题。思路是先构造出 next[] 数组,下标为 i,定义一个变量 t = i - next[i] 就是next数组下标和下标对应值的差,如果这个差能被下标i整除,即 i%t==0 ,则说明下标i之前的字符串(周期性字符串长度为 i)一定可以由一个前缀周期性的表示出来,这个前缀的长度为刚才求得的那个差,即 t,则这个前缀出现的次数为 i/t 。所以最后输出 i 和 i/t 即可。
代码:
1 import java.util.ArrayList; 2 import java.util.List; 3 import java.util.Scanner; 4 5 public class HDU1358 { 6 7 public static void main(String[] args) { 8 Scanner scanner = new Scanner(System.in); 9 List<String> list = new ArrayList<String>(); 10 11 while(true){ 12 int n = scanner.nextInt(); 13 if(n==0) break; 14 String s = scanner.next(); 15 list.add(s); 16 } 17 for(int j = 0;j<list.size();j++){ 18 String s = list.get(j); 19 20 int []next = next(s); 21 System.out.println("Test case #"+(j+1)); 22 boolean flag = false; 23 for(int i=2;i<next.length;i++){ 24 int k = next[i]; 25 int t = i-k; 26 if (i%t==0&&i/t>1) { 27 System.out.println(i +" "+i/t); 28 } 29 } 30 // if (!flag) System.out.println(0+" "+0); 31 System.out.println(); 32 } 33 } 34 35 private static int[] next(String s) { 36 if(s==null||s.length()==0)return null; 37 int[]next = new int[s.length()+1]; 38 next[0] = -1; 39 if(s.length()==1) return next; 40 next[1] = 0; 41 int j = 1; 42 int k = next[j]; 43 while(j<s.length()){ 44 if(k==-1||s.charAt(j)==s.charAt(k)){ 45 next[++j] = ++k; 46 }else { 47 k = next[k]; 48 } 49 } 50 return next; 51 } 52 53 }
结果:
相关文章
- 智慧物流:ZETag云标签入选“中国物联网行业创新产品”榜单
- Linux持久化实操
- 国际乒联泄露马龙和樊振东的信息
- 【ES三周年】Informer实战之持久化K8s事件至ElasticSearch
- 关于服务器端渲染的 Web 应用的 504 错误问题
- 14-RabbitMQ高级特性-TTL
- 15-RabbitMQ高级特性-死信队列
- Shells:一款功能强大的反向Shell快速生成工具
- 攻击者失手,自己杀死了僵尸网络 KmsdBot
- 16-RabbitMQ高级特性-延迟队列
- 18-RabbitMQ高级特性-消息追踪
- 因安装木马化的Win10应用程序,乌克兰政府网络被攻破
- Mongo 线上版本切换方案
- 微软修补了用来传播勒索软件的 Windows 零日漏洞
- 错过半决赛,黑客攻击导致世界杯流媒体FuboTV中断
- Git提交后代码后修改commit信息
- PHP立体安全:一网打尽攻击向量
- client-go 源码分析(1) - discovery模块:discoveryclient获取所有的gv和gvr
- client-go 源码分析(2) - discovery模块:discovery cache
- SharpSCCM:一款利用SCCM实现横向渗透的强大工具