POJ-2406-Power Strings

简介: POJ-2406-Power Strings







Power Strings

Time Limit : 6000/3000ms (Java/Other)   Memory Limit : 131072/65536K (Java/Other)
Total Submission(s) : 96   Accepted Submission(s) : 34

Problem Description

Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).

 


Input

Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

 


Output

For each s you should print the largest n such that s = a^n for some string a.

 


Sample Input

abcd aaaa ababab .

 


Sample Output

1 4 3



题目分析:

意思是有多少个子串构成比如说  aaaa = a^4   ababab=(ab)^3    abcd=(abcd)^1    应该明白了吧!也就是这个字符串能被他的最短子串构成   由kmp ,next表的特点知如果满足  len%(len-p[len])==0  就能由子串构成且子串个数就是 len/(len-p[len])



#include<cstdio>
#include<cstring>
const int M = 1000000+10;
char str[M];
int p[M],a[M],len;
void getp()
{
  int i=0,j=-1;
  p[i]=j;
  while(i<len)
  {
    if(j==-1||str[i]==str[j])
    {
      i++;j++;
      p[i]=j;
    }
    else j=p[j];
  }
}
int main()
{
  while(~scanf("%s",str)&&str[0]!='.')
  {
    len=strlen(str);
    getp();
                if(len%(len-p[len])==0)
      printf("%d\n",len/(len-p[len]));
    else
      printf("1\n");
  }
  return 0;
}















目录
相关文章
|
8月前
|
存储 机器学习/深度学习 人工智能
AllData数据中台核心菜单十二:数据同步平台
杭州奥零数据科技有限公司成立于2023年,专注于数据中台业务,维护开源项目AllData并提供商业版解决方案。AllData提供数据集成、存储、开发、治理及BI展示等一站式服务,支持AI大模型应用,助力企业高效利用数据价值。
AllData数据中台核心菜单十二:数据同步平台
|
10月前
|
前端开发 中间件 程序员
如何尽可能快地上手一个业务or项目
本文简单讲述作者对于“怎么尽可能快地上手一个新业务/项目?”这个问题的个人理解。
142 16
|
缓存 算法 C语言
【C++ 标准查找算法 】C++标准库查找算法深入解析(In-depth Analysis of C++ Standard Library Search Algorithms)
【C++ 标准查找算法 】C++标准库查找算法深入解析(In-depth Analysis of C++ Standard Library Search Algorithms)
231 0
|
12月前
|
C++
SDL基础使用02(加载bmp图片、纹理和渲染)
这篇文章介绍了如何使用SDL库在C++中加载和显示BMP图片,以及如何使用纹理和渲染器进行更高级的图形处理。
162 2
|
12月前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
114 0
数据结构与算法学习十四:常用排序算法总结和对比
|
芯片
stm32f407探索者开发板(十二)——Systick滴答定时器-延时函数讲解
stm32f407探索者开发板(十二)——Systick滴答定时器-延时函数讲解
1018 0
|
存储 缓存 关系型数据库
深度解密 MySQL 的 Buffer Pool
深度解密 MySQL 的 Buffer Pool
230 0
|
算法 数据可视化 调度
基于PSO粒子群优化的车间调度问题求解matlab仿真,输出甘特图
基于PSO粒子群优化的MATLAB仿真解决车间调度问题,输入机器与工作完成时间,输出甘特图与收敛图,实现多机器多任务最优并行调度。使用MATLAB 2022a版本运行,通过模拟鸟群觅食行为,不断更新粒子速度与位置寻找最优解,采用工序编码,总加工时间为适应度函数,实现快速收敛并可视化调度结果。
420 16
|
存储 Docker 容器
Docker工作目录迁移
Docker工作目录迁移
|
数据采集 存储 编解码
LabVIEW用高速数据流盘
LabVIEW用高速数据流盘
140 1