文档章节

ZOJ_1905_Power Strings 进击のkmp

電泡泡
 電泡泡
发布于 2013/07/13 16:56
字数 259
阅读 19
收藏 0
Power Strings Time Limit: 5 Seconds       Memory Limit: 32768 KB

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.


Output

For each s you should print the largest n such that s = a^n for some string a. 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.


Sample Input

abcd
aaaa
ababab
.


Sample Output

1
4
3


#include <iostream>
#include <string>
using namespace std;

int next[1000002];
string str;
int len;

void get_next(string T, int next[])
{
    int i,j;
    next[1]=0;
    j=0;i=1;
    while(i<len)//不要等于m
    {
        if(j==0||T[i]==T[j]){
            ++i;
            ++j;//这个地方完全可以弄到m所以等于的时候不用继续循环
            if(T[i]!=T[j])
                next[i]=j;
            else
                next[i]=next[j];
        }
        else
            j=next[j];
    }
}

int
main()
{
    while(cin>>str && str!="."){
        len=str.length();
        get_next(str, next);
        if(len%(len-next[len])==0)
            cout<<len/(len-next[len])<<endl;
        else
            cout<<"1"<<endl;
    }
    return 0;
}

© 著作权归作者所有

共有 人打赏支持
上一篇: ZOJ_3681_E - Cup 2
下一篇: ×_7_9_2013 G: Matrix
電泡泡
粉丝 24
博文 183
码字总数 69717
作品 0
衡阳
私信 提问
poj 2406 Power Strings

kmp优化过的求next的方法不能直接用 aaaaababab. Sample Output 143 Hint [Submit] [Go Back] [Status] [Discuss] /*===================================================================......

locusxt
2013/12/21
0
0
Gym - 101164K Cutting 哈希+枚举

ACM-ICPC Southeastern European Regional Programming Contest Bucharest, Romania – Vinnytsya, Ukraine October 22, 2016 Problem K Cutting Input File: K.in Output File: standard o......

ProLightsfxjh
2017/07/25
0
0
Gym - 101164C Castle KMP的拓展、next数组+dp、好题

ACM-ICPC Southeastern European Regional Programming Contest Bucharest, Romania – Vinnytsya, Ukraine October 22, 2016 Problem C Castle Input File: C.in Output File: standard ou......

ProLightsfxjh
2017/07/25
0
0
jeecg3.7.8

processAnnotationsJndi 严重: Unable to process JNDI URL [jndi:/localhost/WEB-INF/classes/jeecg/ext-common-template/bootstrap/onetomany/java/%24%7BbussiPackage%7D] for annotatio......

大衣哥
10/15
197
1
Aho-Corasick automaton(AC自动机)解析及其在算法竞赛中的典型应用举例

摘要:   本文主要讲述了AC自动机的基本思想和实现原理,如何构造AC自动机,着重讲解AC自动机在算法竞赛中的一些典型应用。 什么是AC自动机? 如何构造一个AC自动机? AC自动机在算法竞赛中...

Reqaw
08/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

错误: 找不到或无法加载主类

在IDEA的使用过程中,经常断掉服务或者重启服务,最近断掉服务重启时突然遇到了一个启动报错: 错误:找不到或无法加载主类 猜测:1,未能成功编译; 尝试:菜单---》Build---》Rebuild Pro...

安小乐
13分钟前
1
0
vue路由传参,刷新页面,引发的bug

最近遇到一个bug 通过vue路由跳转到页面, 然后接参控制(v-if ),成功显示 而刷新页面,显示失败。 苦苦地找了半天原因,打印参数发现正确,再打印下类型......,路由跳过来会保持传参时的...

hanbb
13分钟前
0
0
【58沈剑 架构师之路】InnoDB,select为啥会阻塞insert?

MySQL的InnoDB的细粒度行锁,是它最吸引人的特性之一。 但是,如《InnoDB,5项最佳实践》所述,如果查询没有命中索引,也将退化为表锁。 InnoDB的细粒度锁,是实现在索引记录上的。 一,Inn...

张锦飞
16分钟前
0
0
冒泡,选择和插入排序比较

/** * 冒泡排序,两层嵌套循环,内层局部比较后,找出最大或者最小数据并交换数据,使其局部有序,外层用于比较剩余元素,相较于选择排序,选择排序相当于是冒泡的一个优化版本(减少了交换...

strict_nerd
17分钟前
0
0
html内联(行内)元素、块级(块状)元素和行内块元素分类

HTML可以将元素分类方式分为内联(行内)元素、块级(块状)元素和行内块元素三种。 注:HTML是标签语言,那么既然是标签,就可以自己定义一些自己元素(如<wode>自定义的元素</wode>等),自...

NB-One
23分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部