扩展KMP的应用
我们发现本题的关键在于如何高效的判断两个同构字符串的大小关系,想到如果能够预处理出每一个同构字符串与原字符串的最长公共前缀,那么直接比较它们不一样的部分就好,扩展KMP正好是用来处理这样的问题的,把原串copy一遍加在其后,在其上跑一遍exKMP的next数组,就预处理出了所有同构字符串与原串之间的最长公共前缀,然后扫一遍直接比较即可。
注意:题目中要求的是不同的数字,将所得的答案除以最小循环节即可
本题中我们学到了如何高效的比较同构字符串的大小,使用exKMP即可,本思想可和最小最大表示法一起考察
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
const int MAXN=2e5+5;
int n,nxt[MAXN];
char s[MAXN];
void getnxt(){
nxt[0]=-1;
int len=strlen(s);
int k=-1,j=0;
while(j<len){
if(k==-1||s[j]==s[k]) nxt[++j]=++k;
else k=nxt[k];
}
}
void getext(){
int len=strlen(s);
nxt[0]=len;
int id=0,mx=0;
for(int i=1;i<len;i++){
if(i>=mx||i+nxt[i-id]>=mx) {
if(i>=mx) mx=i;
while(mx<len&&s[mx]==s[mx-i]) mx++;
nxt[i]=mx-i;
id=i;
}else nxt[i]=nxt[i-id];
}
}
int main(){
freopen("in.txt","r",stdin);
cin>>n;
int cnt=0;
while(n--){
scanf("%s",s);
int len=strlen(s);
getnxt();
int ans=len-nxt[len],tt;
if(len%ans==0) tt=len/ans;
else tt=1;
for(int i=0;i<len;i++) s[len+i]=s[i];
s[len*2]='\0';
getext();
int num1=0,num2=0,num3=0;
for(int i=0;i<len;i++){
if(nxt[i]>=len) num2++;
else if(s[nxt[i]]>s[nxt[i]+i]) num1++;
else num3++;
}
printf("Case %d: %d %d %d\n",++cnt,num1/tt,num2/tt,num3/tt);
}
fclose(stdin);
return 0;
}
HDU 4333 Revolving Digits的更多相关文章
-
HDU 4333 Revolving Digits 扩张KMP
标题来源:HDU 4333 Revolving Digits 意甲冠军:求一个数字环路移动少于不同数量 等同 于的数字 思路:扩展KMP求出S[i..j]等于S[0..j-i]的最长前缀 推断 nex ...
-
字符串(扩展KMP):HDU 4333 Revolving Digits
Revolving Digits Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) ...
-
扩展KMP - HDU 4333 Revolving Digits
Revolving Digits Problem's Link Mean: 给你一个字符串,你可以将该字符串的任意长度后缀截取下来然后接到最前面,让你统计所有新串中有多少种字典序小于.等于.大于原串. ...
-
Hdu 4333 Revolving Digits(Exkmp)
Revolving Digits Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) To ...
-
HDU 4333 Revolving Digits 扩展KMP
链接:http://acm.hdu.edu.cn/showproblem.php?pid=4333 题意:给以数字字符串,移动最后若干位到最前边,统计得到的数字有多少比原来大,有多少和原来同样,有多少 ...
-
HDU - 4333 Revolving Digits(扩展KMP)
http://acm.hdu.edu.cn/showproblem.php?pid=4333 题意 一个数字,依次将第一位放到最后一位,问小于本身的数的个数及等于本身的个数和大于本身的个数,但是要注意 ...
-
【扩展kmp+最小循环节】HDU 4333 Revolving Digits
http://acm.hdu.edu.cn/showproblem.php?pid=4333 [题意] 给定一个数字<=10^100000,每次将该数的第一位放到放到最后一位,求所有组成的不同的 ...
-
HDU 4333 Revolving Digits [扩展KMP]【学习笔记】
题意:给一个数字,每一次把它的最后一位拿到最前面,一直那样下去,分别求形成的数字小于,等于和大于原来数的个数. SAM乱搞失败 当然要先变SS了 然后考虑每个后缀前长为n个字符,把它跟S比较就行了 如 ...
-
hdu 4333";Revolving Digits";(KMP求字符串最小循环节+拓展KMP)
传送门 题意: 此题意很好理解,便不在此赘述: 题解: 解题思路:KMP求字符串最小循环节+拓展KMP ①首先,根据KMP求字符串最小循环节的算法求出字符串s的最小循环节的长度,记为 k: ②根据拓展 ...
随机推荐
-
python基础(1) 变量类型
变量赋值: python中的变量不需要类型声明 每个变量在使用前必须赋值,变量赋值以后才会被创建 变量在内存中创建时,包括变量的标识.名称和数据这些信息. EX: #!/usr/bin/python ...
-
Html总结及日志目录
Html就是超文本标记语言的简写,是最基础的网页语言,代码都是由标签所组成,不用区分大小写. 1. Html代码由<html>开始</html>结束.里面由头部分<hea ...
-
登陆中session的处理
在学校中的登陆注册使用的普通session存储信息,然后就是根据session中获取user是否拥有来判断是否登陆. 在一次面试中别人问到了我你们项目的登陆session是怎么一个情况,我这样答的话那 ...
-
【C#学习笔记】文本复制到粘贴板
using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; usin ...
-
svnserve: E000098: 不能绑定服务器套接字: 地址已在使用
百度一下,所有资料都是 1.查找出目前正在使用的svnserve进程,然后kill掉 ps -aux | grep svnserve kill -9 xxx // xxx代表svnserve对 ...
-
Axure RP8 注册码
升级了 8.1.0.3381版本后,需要使用下面这组注册码 License:zdfansKey:fZw2VoYzXakllUuLVdTH13QYWnjD6NZrxgubQkaRyxD5+HNMqdr+ ...
-
spring boot2 kafka
一.软件版本 1.linux:centos6 2.zookeeper:zookeeper-3.4.1 3.kafka:kafka_2.12-2.2.0 4.jdk:1.8 5.instelliJ Id ...
-
python - hadoop,mapreduce demo
Hadoop,mapreduce 介绍 59888745@qq.com 大数据工程师是在Linux系统下搭建Hadoop生态系统(cloudera是最大的输出者类似于Linux的红帽), 把用户的交易 ...
-
【转】【WPF】WPF - MVVM - 如何将ComboBox的Selectchange事件binding到ViewModel
将所有的事件,属性,都映射到ViewModel中.好处多多,以后开发尽量用这种模式. 解决方法: 使用System.Windows.Interactivity.dll,添加该dll到项目引用 xmln ...
-
HTTP Header之Content-Type
HTTP Header之Content-Type 目录 1. HTTP Header 2. 文件请求和接口请求 3. 几种 Content-Type 3.1 application/x-www-f ...