Power Strings----poj2406(kmp扩展 循环节)
2024-08-24 18:29:21
题目链接:http://poj.org/problem?id=2406
题意:就是求串s能够最多由多少个相同的串a串联而成;
例如 ababab 由3个ab串联而成;
abababa 只能由1个abababa组成;
kmp中的Next[n](下标从0开始)表示n个元素的前缀和后缀的最大匹配;
a b a b a b a b
0 1 2 3 4 5 6 7
0-5和2-7是最大匹配Next【n】= 6;ab就是循环节(因为n/(n-next[n])是整数,所以是循环节)即 n - Next【n】;
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std; #define N 1000010 char s[N];
int Next[N], n; void Getnext()
{
int i = , j = -;
Next[] = -;
while(i<n)
{
if(j==- || s[i] == s[j])
Next[++i] = ++j;
else
j=Next[j];
}
} int main()
{
while(scanf("%s", s),s[]!='.')
{
n = strlen(s); Getnext(); int ans = n-Next[n]; if(n%ans!=)
ans = ;
else
ans = n/ans;
printf("%d\n", ans);
}
return ;
}
/*
aabaabaa
1
*/
最新文章
- kali 安装ss代理客户端的方法(纯属个人总结)
- Root--超级用户
- django数据库的增删改查
- Expression Blend4经验分享:文字公告无缝循环滚动效果
- CentOS7 win7 u盘装双系统 修复系统
- 自定义ActionBar
- ubuntn 安装 MySQL
- ios 指南针
- java设计模式--原始模型模式
- vim配置python开发环境
- java基本对象Integer,String比较相等及equal案例说明
- Android单位度量
- 从现在开始使用nodejs开发的几点答疑
- Android getTopActivity的方法
- 读书笔记---HTML5实战 MARCO CASARIO(后六章)
- Do You Kown Asp.Net Core -- Asp.Net Core 2.0 未来web开发新趋势 Razor Page
- mysql 关联查询技巧
- css的定义、用法、注释、命名规则、书写规范
- Echarts 报错:Uncaught Error: [MODULE_MISS]";echarts/config"; is not exists!
- Vue之vue-cli安装与简单调试