POJ2406:Power Strings——题解
2024-08-26 05:17:22
http://poj.org/problem?id=2406
就是给一个串,求其循环节的个数。
稍微想一下就知道,KMP中nxt数组记录了所有可与前面匹配的位置。
那么如果我们的循环节长度为k,有n个,那么我们最后一个nxt显然就会是k*(n-1)。
倒推即可。
#include<cstdio>
#include<cstring>
using namespace std;
char s2[];
int nxt[]={};
void getnext(int m){
int j=;
for(int i=;i<=m;i++){
while(j!=&&s2[j+]!=s2[i])j=nxt[j];
if(s2[j+]==s2[i])j++;
nxt[i]=j;
}
return;
}
int main(){
while(scanf("%s",s2+)!=EOF){
if(s2[]=='.')break;
memset(nxt,,sizeof(nxt));
int m=strlen(s2+);
getnext(m);
int ans=;
if(m%(m-nxt[m])==){
ans=m/(m-nxt[m]);
}
printf("%d\n",ans);
}
return ;
}
最新文章
- MSSQL FOR MXL PATH 运用(转载)
- java后台调用HttpURLConnection类模拟浏览器请求(一般用于接口调用)
- 怎样让你的代码更好的被JVM JIT Inlining
- (原)Struts 相关资源下载
- 读书笔记之 - javascript 设计模式 - 工厂模式
- Notepad++强大的代码补全和代码提示功能的方法
- c#扩展方法的使用,实现的几个功能
- Azure CosmosDB (5) 高可用性
- vue的事件处理梳理
- Tools - 正版Windows7系统的下载与安装
- Python自制微信机器人:群发消息、自动接收好友
- ASP.NET WebForm 检测页面刷新(Refresh)
- PHP获取文件后缀名
- Effective Java 第三版——53. 明智而审慎地使用可变参数
- SAP 数据类型
- MT【176】两两乘积
- 模拟界面请求到web服务器
- Jquery API学习笔记
- Java移位运算符 “
- springboot-vue-JWT使用