题目链接: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
*/

最新文章

  1. kali 安装ss代理客户端的方法(纯属个人总结)
  2. Root--超级用户
  3. django数据库的增删改查
  4. Expression Blend4经验分享:文字公告无缝循环滚动效果
  5. CentOS7 win7 u盘装双系统 修复系统
  6. 自定义ActionBar
  7. ubuntn 安装 MySQL
  8. ios 指南针
  9. java设计模式--原始模型模式
  10. vim配置python开发环境
  11. java基本对象Integer,String比较相等及equal案例说明
  12. Android单位度量
  13. 从现在开始使用nodejs开发的几点答疑
  14. Android getTopActivity的方法
  15. 读书笔记---HTML5实战 MARCO CASARIO(后六章)
  16. Do You Kown Asp.Net Core -- Asp.Net Core 2.0 未来web开发新趋势 Razor Page
  17. mysql 关联查询技巧
  18. css的定义、用法、注释、命名规则、书写规范
  19. Echarts 报错:Uncaught Error: [MODULE_MISS]&quot;echarts/config&quot; is not exists!
  20. Vue之vue-cli安装与简单调试

热门文章

  1. MultipartEntity 乱码
  2. phpstrom直接运行和调试php
  3. Python中import和from import
  4. XML-RPC使用手册
  5. MySQL线程池总结
  6. Hadoop源码分析之Configuration
  7. 人脸验证算法Joint Bayesian详解及实现(Matlab)
  8. 【BZOJ】1500: [NOI2005]维修数列(splay+变态题)
  9. ThinkPHP项目笔记之RBAC(权限)中篇
  10. 【基础练习】【BFS+A*】codevs1225八数码难题题解