文档章节

ZOJ_1905_Power Strings 进击のkmp

電泡泡
 電泡泡
发布于 2013/07/13 16:56
字数 259
阅读 19
收藏 0
点赞 0
评论 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;
}

© 著作权归作者所有

共有 人打赏支持
電泡泡
粉丝 25
博文 181
码字总数 69717
作品 0
衡阳
poj 2406 Power Strings

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

locusxt ⋅ 2013/12/21 ⋅ 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

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

有谁帮我解决这个问题啊。。。。就是关于用jsoup提取多个url 把这写url放在一个字段中、、、、

怎么把下面的代码给提取出来。。放在一个字段里面: 要求是把下面的每个p标签放在一个字段中。。下面有2个p标签就放在2个字段中。。。。。把url给提取出来。。。 推荐播放:

很好 ⋅ 2012/07/04 ⋅ 2

デスクトップ仮想化とWindowsライセンス

仮想化とライセンス 前回まで説明してきました、デスクトップ仮想化およびアプリケーション仮想化ですが、物理的な展開に対して注意しなければならない点がいくつかあります。その一つが『ラ...

剑气满天 ⋅ 2015/09/02 ⋅ 1

ACM Summer Training Warm up

ACM Summer Training Warm up Cover 热身水题 题目 HDU 4500 小Q系列故事——屌丝的逆袭 思路 简单的模拟,一个数组读入数据,一个数组计算维护结果 HDU 2109 Fighting for HDU 思路 简单排序...

SpiffyEight77 ⋅ 2017/08/14 ⋅ 0

collectd 5.5.3 发布,系统监控和统计工具

collectd 5.5.3 发布了,这将是十二月份 5.7 发布之前 5.5.x的最后一个修正版。 主要更新如下: collectd: Write threads are stopped before shutdown callbacks are called. Thanks to Fl...

两味真火 ⋅ 2016/11/29 ⋅ 1

Eova 1.5.1 Oracle 兼容,Java Web 快速开发平台

主要兼容Oracle,Mysql用户自行判定是否有更新必要! 兼容Oracle,提供Oracle完整脚本、配置,可直接运行! [新增]可在界面直接配置多子表 [新增]排除不需要登录拦截的URL // 不需要登录拦截...

Jieven ⋅ 2016/02/16 ⋅ 14

ZOJ Problem Set - 1944 Tree Recovery(二叉树三种遍历知二求三)

Tree Recovery Time Limit: 2 Seconds Memory Limit: 65536 KB Little Valentine liked playing with binary trees very much. Her favorite game was constructing randomly looking binary......

hushhw ⋅ 2017/11/27 ⋅ 0

求解电影网视频地址解密key,解析过程已罗列(未完结求助)

-------------------------------------------------- 整理记录 视频网页:http://www.1905.com/vod/play/974839.shtml 从网页中取到VODCONFIG配置信息 譬如:vid : "974839", [vid_1] = vid......

Eller ⋅ 2016/03/19 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

用ZBLOG2.3博客写读书笔记网站能创造今日头条的辉煌吗?

最近两年,著名的自媒体网站今日头条可以说是火得一塌糊涂,虽然从目前来看也遇到了一点瓶颈,毕竟发展到了一定的规模,继续增长就更加难了,但如今的今日头条规模和流量已经非常大了。 我们...

原创小博客 ⋅ 29分钟前 ⋅ 0

MyBatis四大核心概念

本文讲解 MyBatis 四大核心概念(SqlSessionFactoryBuilder、SqlSessionFactory、SqlSession、Mapper)。 MyBatis 作为互联网数据库映射工具界的“上古神器”,训有四大“神兽”,谓之:Sql...

waylau ⋅ 49分钟前 ⋅ 0

以太坊java开发包web3j简介

web3j(org.web3j)是Java版本的以太坊JSON RPC接口协议封装实现,如果需要将你的Java应用或安卓应用接入以太坊,或者希望用java开发一个钱包应用,那么用web3j就对了。 web3j的功能相当完整...

汇智网教程 ⋅ 今天 ⋅ 0

2个线程交替打印100以内的数字

重点提示: 线程的本质上只是一个壳子,真正的逻辑其实在“竞态条件”中。 举个例子,比如本题中的打印,那么在竞态条件中,我只需要一个方法即可; 假如我的需求是2个线程,一个+1,一个-1,...

Germmy ⋅ 今天 ⋅ 0

Springboot2 之 Spring Data Redis 实现消息队列——发布/订阅模式

一般来说,消息队列有两种场景,一种是发布者订阅者模式,一种是生产者消费者模式,这里利用redis消息“发布/订阅”来简单实现订阅者模式。 实现之前先过过 redis 发布订阅的一些基础概念和操...

Simonton ⋅ 今天 ⋅ 0

error:Could not find gradle

一.更新Android Studio后打开Project,报如下错误: Error: Could not find com.android.tools.build:gradle:2.2.1. Searched in the following locations: file:/D:/software/android/andro......

Yao--靠自己 ⋅ 昨天 ⋅ 0

Spring boot 项目打包及引入本地jar包

Spring Boot 项目打包以及引入本地Jar包 [TOC] 上篇文章提到 Maven 项目添加本地jar包的三种方式 ,本篇文章记录下在实际项目中的应用。 spring boot 打包方式 我们知道,传统应用可以将程序...

Os_yxguang ⋅ 昨天 ⋅ 0

常见数据结构(二)-树(二叉树,红黑树,B树)

本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树 写在前面 本文所有图片均截图自coursera上普林斯顿的课程《Algorithms, Part I》中的Slides 相关命题的证明可参考《算法(第...

浮躁的码农 ⋅ 昨天 ⋅ 0

android -------- 混淆打包报错 (warning - InnerClass ...)

最近做Android混淆打包遇到一些问题,Android Sdutio 3.1 版本打包的 错误如下: Android studio warning - InnerClass annotations are missing corresponding EnclosingMember annotation......

切切歆语 ⋅ 昨天 ⋅ 0

eclipse酷炫大法之设置主题、皮肤

eclipse酷炫大法 目前两款不错的eclipse 1.系统设置 Window->Preferences->General->Appearance 2.Eclipse Marketplace下载【推荐】 Help->Eclipse Marketplace->搜索‘theme’进行安装 比如......

anlve ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部