POJ 2406 Power String
2024-10-19 12:42:30
算出next数组.
对于任何一个循环字串,len-next[len]必为最小循环节长度
若len%(len-next[len])==0
即为循环字串,n=len/(len-next[len])
否则输出1
代码:
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+;
char str[N];
int next[N],ans,len;
void make()
{
int i=,j=-;
next[i]=j;
while(i<len)
{
if(j==-||str[i]==str[j])
{
i++;
j++;
next[i]=j;
}
else
j=next[j];
}
}
int main()
{
while(~scanf("%s",str))
{
if(str[]=='.') break;
len=strlen(str);
make();
int k=next[len];
if(!(len%(len-k)))
printf("%d\n",len/(len-k));
else
printf("1\n");
}
return ;
}
最新文章
- python异常和错误(syntax errors 和 exceptions)
- Leetcode 110 Balanced Binary Tree 二叉树
- [开发笔记]-DataGridView控件中自定义控件的使用
- Oracle 12C RAC的optimizer_adaptive_features造成数据插入超时
- ASP.NET Eval四种绑定方式
- Spring配置文件web.xml关于拦截
- C#算法基础之希尔排序
- Spring的工作原理核心组件和应用
- hdu_4787_GRE Words Revenge(在线AC自动机)
- linux文件相关的命令
- 【笔记】HybridApp中使用Promise化的JS-Bridge
- selenium修改cookie
- ABP中mapping中忽略属性
- Java基础:整型数组(int[]、Integer[])排序
- hive中 regexp_replace的用法,替换特殊字符问题
- jQuery实现评论弹幕、弹幕漂浮、滚动代码
- redis学习(五) redis过期时间
- HDU 4731 Minimum palindrome (2013成都网络赛,找规律构造)
- JAVA并发:深入分析volatile
- Unity3d OnApplicationPause与OnApplicationFocus