链接:
http://acm.hust.edu.cn/problem.php?id=1010
题目:
Description
There is a string A. The length of A is less than 1,000,000. I rewrite it again and again. Then I got a new string: AAAAAA...... Now I cut it from two different position and get a new string B. Then,
give you the string B, can you tell me the length of the shortest possible string A.
For example, A="abcdefg". I got abcdefgabcdefgabcdefgabcdefg.... Then I cut the red part: efgabcdefgabcde as string B. From B, you should find out the shortest A.
Input
Multiply Test Cases.
For each line there is a string B which contains only lowercase and uppercase charactors.
The length of B is no more than 1,000,000.
Output
For each line, output an integer, as described above.
Sample Input
bcabcab
efgabcdefgabcde
Sample Output
3
7
题目大意:
有一个字符串A,假设A是“abcdefg”, 由A可以重复组成无线长度的AAAAAAA,即“abcdefgabcdefgabcdefg.....”.
从其中截取一段“abcdefgabcdefgabcdefgabcdefg”,取红色部分为截取部分,设它为字符串B。
现在先给出字符串B, 求A最短的长度。
分析与总结:
设字符串C = AAAAAAAA.... 由于C是由无数个A组成的,所以里面有无数个循环的A, 那么从C中的任意一个起点开始,也都可以有一个循环,且这个循环长度和原来的A一样。(就像一个圆圈,从任意一点开始走都能走回原点)。
所以,把字符串B就看成是B[0]为起点的一个字符串,原问题可以转换为:求字符串B的最短循环节点。
根据最小循环节点的求法,很容易就可以求出这题。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1000005;
char T[MAXN];
int f[MAXN];
void getFail(char *p,int *f){
int n=strlen(p);
f[0]=f[1]=0;
for(int i=1; i<n; ++i){
int j=f[i];
while(j && p[i]!=p[j]) j=f[j];
f[i+1] = p[i]==p[j]?1+j:0;
}
}
int main(){
while(gets(T)){
getFail(T,f);
int n=strlen(T);
printf("%d\n", n-f[n]);
}
return 0;
}
—— 生命的意义,在于赋予它意义士。
原创http://blog.csdn.net/shuangde800,By
D_Double (转载请标明)
分享到:
相关推荐
HUSTOJ-SAE 安装次数 : 110 本系统为Online Judge 系统,可广泛用于教学、竞赛、招聘等用途。 九度OJ为本系统改造的典型案例。 文档、社区服务见项目首页,http://code.google.com/p/hustoj/ 安装应用 下载应用...
计算机数据表示实验(HUST)
计算机数据表示实验(HUST) 1_9data代码
基于bootstrap对hustoj前端的二次改造
HUST ACM OnlineJudge HUSTOJ ,开源 全部采用开源技术,不仅仅是提供源代码,搭建HUSTOJ?不需要购买任何商业软件。采用成熟的Li...
登录ssh,执行安装脚本:wget http://dl.hustoj.com/install-ubuntu-bt.shsudo bash install-ubu
HUSTOJ搭建(ACM测评系统).pdf
ubuntu 16.04安装hustoj,一种详细的部署与实现方案,通过自己总结实现的技巧。
HUSTOJ特性 开源 全部采用开源技术,不仅仅是提供源代码,搭建HUSTOJ?不需要购买任何商业软件。 采用成熟的Linux32位系统平台,通过目录锁定和用户锁定以及系统调用限制避免恶意答案损害系统。 支持负载均衡,可以将...
计算机数据表示实验(HUST)
简介当配置为启用抄袭检查时,judge_client 将调用 sim,判断相似性结果,并写回数据库或sim 为第三方应用程序,可进行语法分析判断文本相似度,通过
全部能用
logisim-hust-20200118.exe
华中科技大学HUST类MIPS单周期微处理器设计实验报告.pdf华中科技大学HUST类MIPS单周期微处理器设计实验报告.pdf华中科技大学HUST类MIPS单周期微处理器设计实验报告.pdf华中科技大学HUST类MIPS单周期微处理器设计实验...
计算机组成与系统结构实践项目,华中科大计算机学院实践课:计算机组成与系统结构实践项目: 1、汉字字库存储芯片扩展实验 2、MIPS寄存器文件设计 3、MIPS RAM设计 4、全相联cache设计 5、直接相联cache设计 ...
HUST1.txt 以下内容因还在构建中,还请谅解…… 第6关:单周期CPU单级中断机制设计(构建中) 第7关:单周期CPU多级中断机制设计---硬件堆栈(构建中) 第8关:单周期CPU多级中断机制设计---内存堆栈(构建中)
全部关卡,复制txt,满分过
tar zxf install.r2133.tar.gz cd install sudo bash install-interactive.sh
头歌计算机数据表示实验(HUST)9关通过全代码
HUST I3 数控编程和连接相关资料zip,HUST I3 数控编程和连接相关资料