点击打开链接hust1010
思路:kmp+最小循环节
分析:
1 题目要求的是,有一个字串A,现在利用A组成了一个新的字符串AAAAA...,现在从这个新的字符串的两个不同位置剪下去得到字符串B,问A的最小长度
2 由于B里面的字符都是来自A,那么如果要A最小那么最小值就是等于B的最小循环节。
3 直接对B求最小循环节
代码:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 1000010
char pattern[MAXN];
int next[MAXN];
void getNext(){
int m = strlen(pattern);
next[0] = next[1] = 0;
for(int i = 1 ; i < m ; i++){
int j = next[i];
while(j && pattern[i] != pattern[j])
j = next[j];
next[i+1] = pattern[i] == pattern[j] ? j+1 : 0;
}
int cir = m-next[m];
printf("%d\n" , cir);
}
int main(){
while(scanf("%s" , pattern) != EOF)
getNext();
return 0;
}
分享到:
相关推荐
HUSTOJ-SAE 安装次数 : 110 本系统为Online Judge 系统,可广泛用于教学、竞赛、招聘等用途。 九度OJ为本系统改造的典型案例。 文档、社区服务见项目首页,http://code.google.com/p/hustoj/ 安装应用 下载应用...
计算机数据表示实验(HUST)
HUST ACM OnlineJudge HUSTOJ ,开源 全部采用开源技术,不仅仅是提供源代码,搭建HUSTOJ?不需要购买任何商业软件。采用成熟的Li...
计算机数据表示实验(HUST) 1_9data代码
登录ssh,执行安装脚本:wget http://dl.hustoj.com/install-ubuntu-bt.shsudo bash install-ubu
ubuntu 16.04安装hustoj,一种详细的部署与实现方案,通过自己总结实现的技巧。
HUSTOJ搭建(ACM测评系统).pdf
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设计 ...
基于bootstrap对hustoj前端的二次改造
tar zxf install.r2133.tar.gz cd install sudo bash install-interactive.sh
头歌计算机数据表示实验(HUST)9关通过全代码
HUST I3 数控编程和连接相关资料zip,HUST I3 数控编程和连接相关资料
全部关卡,复制txt,满分过